×

Sequencing a hybrid two-stage flowshop with dedicated machines. (English) Zbl 1064.90545

Summary: We treat the \(n\)-job, two-stage hybrid flowshop problem with one machine in the first stage and two different machines in parallel in the second stage. The objective is to minimize the makespan. We demonstrate that the problem is NP-complete. We formulate a dynamic program, which is beyond our grasp for problems of more than 15 jobs. Our search for heuristic approaches led to the adoption of the Johnson sequence, which motivated two of the three approaches: dynamic programming and sequence-and-merge. The third approach, the greedy heuristic, was included as example of an elementary heuristic.

MSC:

90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1080/09537289408919506 · doi:10.1080/09537289408919506
[2] DOI: 10.1016/S0166-3615(98)00073-6 · doi:10.1016/S0166-3615(98)00073-6
[3] BIAZIWICZ J., Scheduling Computer and Manufacturing Process (1996)
[4] BOTTA-GENOULAZ V., Planification et ordonnancement d’une succession d’ateliers avec contraintes (1996)
[5] DOI: 10.1016/0377-2217(91)90148-O · Zbl 0732.90040 · doi:10.1016/0377-2217(91)90148-O
[6] BUTEN, R. E. and SHEN, V. Y. A scheduling model for computer systems with two multiprocessors. Proceedings of the Sagomore Computer Conference on Parallel Processing. pp.130–138.
[7] DOI: 10.1287/mnsc.16.10.B630 · Zbl 0194.50504 · doi:10.1287/mnsc.16.10.B630
[8] ELMAGHRABY S. E., Report No. 27695-7906, in: Sequencing jobs on two-stage hybrid flowshop with identical machines to minimize makespan (1998)
[9] DOI: 10.1287/moor.1.2.117 · Zbl 0396.90041 · doi:10.1287/moor.1.2.117
[10] DOI: 10.1080/002075497194868 · Zbl 0945.90594 · doi:10.1080/002075497194868
[11] DOI: 10.1080/07408179608966258 · doi:10.1080/07408179608966258
[12] HERRMANN J. W., Report No. 92-23, in: Three-machine look-ahead scheduling problems (1992)
[13] DOI: 10.1002/nav.3800010110 · Zbl 1349.90359 · doi:10.1002/nav.3800010110
[14] DOI: 10.1016/0167-6377(94)90026-4 · Zbl 0812.90066 · doi:10.1016/0167-6377(94)90026-4
[15] DOI: 10.1080/09537289608930370 · doi:10.1080/09537289608930370
[16] DOI: 10.1080/00207548408942479 · doi:10.1080/00207548408942479
[17] DOI: 10.1287/opre.27.2.290 · doi:10.1287/opre.27.2.290
[18] RIANE F., Scheduling hybrid flowshops: algorithms and applications (1998)
[19] RIANI, F. and ARTIBA, A. Scheduling multi-stage flowshop problem: stale of the art. International Conference on Industrial Engineering and Production Management. H. pp.323–335.
[20] RIANI, F., ARHBA, A. and ELMAGHRABY, S. E. Sequencing on hybrid fluwshop to minimize makespan. Proceedings of the First International Conference on Operations and Quantitative Management. Jaipur, II. pp.572–579.
[21] SALVADOR M. S., Symposium of the Theorv of Scheduling and Applications pp 83– (1973) · doi:10.1007/978-3-642-80784-8_7
[22] SHUN, V. Y. and CHUN, Y. E. A scheduling strategy for the flowshop problem in a system with two classes of processors. Proceedings of the Conference on Information und System Science. pp.645–649.
[23] DOI: 10.1051/ro:1999108 · Zbl 0960.90042 · doi:10.1051/ro:1999108
[24] DOI: 10.1287/opre.36.3.445 · Zbl 0646.90039 · doi:10.1287/opre.36.3.445
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.