๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Counterexamples to optimal permutation schedules for certain flow shop problems

โœ Scribed by S. S. Panwalkar; M. L. Smith; C. R. Woollam

Publisher
John Wiley and Sons
Year
1981
Tongue
English
Weight
117 KB
Volume
28
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

It is well known that a minimal makespan permutation sequence exists for the n ร— 3 flow shop problem and for the n ร— m flow shop problem with no inprocess waiting when processing times for both types of problems are positive. It is shown in this paper that when the assumption of positive processing times is relaxed to include nonnegative processing times, optimality of permutation schedules cannot be guaranteed.

๐Ÿ“œ SIMILAR VOLUMES

Asymptotically optimal schedules for sin
Asymptotically optimal schedules for single-server flow shop problems with setup costs and times
โœ S.M.R. Iravani; C.P. Teo ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 221 KB

We consider the processing of M jobs in a flow shop with N stations in which only a single server is in charge of all stations. We demonstrate that for the objective of minimizing the total setup and holding cost, a class of easily implementable schedules is asymptotically optimal.