Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops (Q4033755)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 166199
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops |
scientific article; zbMATH DE number 166199 |
Statements
Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops (English)
0 references
16 May 1993
0 references
fixed completion time
0 references
open shop
0 references
flow shop
0 references
mean job completion time
0 references
job preemption
0 references
polynomial algorithms
0 references
NP-hardness
0 references
0.8932902216911316
0 references
0.880300760269165
0 references
0.8701305389404297
0 references
0.8674870729446411
0 references
0.8667904734611511
0 references
The authors analyse two machine open shop and flow shop scheduling problems. The objective is to minimize the mean job completion time and job preemption is possible. Whereas these two problems on three machines are known to be NP-hard in the strong sense, the complexity status of the two machine problems has been unsolved. In this article, the authors prove that the two machine open shop problem is NP-hard in the ordinary sense and the flow shop problem is NP-hard in the strong sense. Moreover, for a fixed sequence of job completion times, polynomial algorithms are developed to compute the associated optimal schedule. The complexities of these two algorithms are \(O(n)\) for the open shop and \(O(n\cdot\log n)\) for the flow shop problem, respectively; here \(n\) denotes the number of jobs. It is interesting that the NP-hardness proof for the two machine flow shop problem provides an alternative proof for the NP-hardness (in the strong sense) of the associated non-preemptive problem.
0 references