Flow shop and open shop scheduling with a critical machine and two operations per job. (English) Zbl 0991.90073
Summary: This paper develops polynomial time algorithms to solve the \(m\) machine flow shop and open shop makespan problems with a critical machine (that processes all jobs) and at most two operations per job under certain assumptions. In the flow shop case, an \(O(m(n\log n+\log m))\) algorithm is developed (where \(n\) is the number of jobs) assuming that all jobs that require processing on the same subset of machines are contiguously processed. In the open shop case, an \(O(n+ m\log m)\) algorithm is developed assuming that the load on the critical machine exceeds the load on any other machine.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 65Y20 | Complexity and performance of numerical algorithms |
| 90C27 | Combinatorial optimization |
Keywords:
polynomial time algorithmsReferences:
| [1] | Gonzalez, T.; Sahni, S., Open shop scheduling to minimize finish time, Journal of the Association for Computing Machinery, 23, 665-679 (1976) · Zbl 0343.68031 |
| [2] | Gonzalez, T.; Sahni, S., Flowshop and jobshop schedules: Complexity and approximation, Operations Research, 26, 36-52 (1978) · Zbl 0371.90061 |
| [3] | Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359 |
| [4] | Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., 1993. Sequencing and scheduling: algorithms and complexity, in: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (Eds.), Handbooks in Operations Research and Management Science, vol. 4, Logistics of Production and Inventory. North-Holland, Amsterdam, pp. 445-522; Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., 1993. Sequencing and scheduling: algorithms and complexity, in: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (Eds.), Handbooks in Operations Research and Management Science, vol. 4, Logistics of Production and Inventory. North-Holland, Amsterdam, pp. 445-522 · Zbl 0798.90028 |
| [5] | Liu, C. Y.; Bulfin, R. L., Scheduling ordered open shops, Computers and Operations Research, 14, 257-264 (1987) · Zbl 0625.90045 |
| [6] | Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification Complexity and Computations (1976), Nijhoff: Nijhoff The Hague |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
