The two-machine sequence dependent flowshop scheduling problem (Q1081528)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The two-machine sequence dependent flowshop scheduling problem |
scientific article; zbMATH DE number 3970492
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The two-machine sequence dependent flowshop scheduling problem |
scientific article; zbMATH DE number 3970492 |
Statements
The two-machine sequence dependent flowshop scheduling problem (English)
0 references
1986
0 references
This paper considers the static two-machine flowshop scheduling problem where the setup times of jobs depend on immediately preceding jobs and shows that the problem is NP-complete. It is shown that permutation schedules for this problem do not always minimize makespan. Conditions are specified which will prove the optimality of a permutation schedule. Four efficient approximate algorithms are proposed to find approximate schedules for the problem and are empirically evaluated to assess their effectiveness in finding a minimum makespan permutation schedule.
0 references
static two-machine flowshop scheduling
0 references
makespan
0 references
optimality of a permutation schedule
0 references
approximate algorithms
0 references
0 references
