| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10523109 | Computers & Industrial Engineering | 2005 | 6 Pages |
Abstract
This paper considers the evaluation of the worst-case performance ratio between the best solution of the flow shop problem and the permutation flow shop with time delays considerations. It is observed that, even in the restricted case of two machines and unit execution time operations, the two models may generate different optimal values for the makespan. More specifically, it is shown that, in the two-machine case, the performance ratio between the best permutation schedule and the best flow shop schedule is bounded by 2. When the operations of the n jobs are restricted to be unit execution time, this ratio is reduced to (2â(3/n+2)) for the two-machine case, and is m for the m-machine case.
Related Topics
Physical Sciences and Engineering
Engineering
Industrial and Manufacturing Engineering
Authors
D. Rebaine,