Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time. (English) Zbl 0927.90033
Summary: The problem of scheduling independent jobs on several serial workshops consisting of identical parallel machines is studied. Each job is processed by one machine in each workshop. This workshop environment is called a hybrid Flowshop. Each job has its own due-date and the objective is to minimize maximum tardiness or maximum completion time. Given that the problem is NP-hard, a set of list algorithms is developed to solve it. To evaluate the quality of these heuristics, lower bounds on the optimal solution have been derived and compared to the value of the heuristics on 1920 problems. Our results indicate that a heuristic based on Nawaz et al. (1983) method outperformed the other approaches.
References:
| [1] | DOI: 10.1007/BF02277185 · Zbl 0456.68042 · doi:10.1007/BF02277185 |
| [2] | DOI: 10.1287/mnsc.16.10.B630 · Zbl 0194.50504 · doi:10.1287/mnsc.16.10.B630 |
| [3] | DOI: 10.1016/0377-2217(90)90215-W · Zbl 0707.90053 · doi:10.1016/0377-2217(90)90215-W |
| [4] | DOI: 10.1287/mnsc.25.12.1208 · Zbl 0465.90046 · doi:10.1287/mnsc.25.12.1208 |
| [5] | FRENCH S., Sequencing and scheduling An introduction to the mathematics of the job-shop (1982) · Zbl 0479.90037 |
| [6] | GRABOWSKI J., Journal of the Operations Research Society 34 pp 615– (1983) |
| [7] | GRABOWSKI J., Opsearch 17 pp 133– (1980) |
| [8] | GUINET A., International Journal of Production Research (1996) |
| [9] | GUINET A., Journal of the Operations Research Society 42 pp 655– (1991) · Zbl 0729.90754 |
| [10] | DOI: 10.1080/00207549108948025 · doi:10.1080/00207549108948025 |
| [11] | GUPTA J. N. D., Journal of the Operations Research Society 39 pp 359– (1988) |
| [12] | DOI: 10.1016/0377-2217(94)90333-6 · Zbl 0800.90570 · doi:10.1016/0377-2217(94)90333-6 |
| [13] | JACKSON , J. R. 1955 , Scheduling a production line to minimize maximum tardiness . Research Report 43 , University of California , Los Angeles . |
| [14] | DOI: 10.1002/nav.3800010110 · Zbl 1349.90359 · doi:10.1002/nav.3800010110 |
| [15] | DOI: 10.1016/0167-6377(82)90021-9 · Zbl 0489.90053 · doi:10.1016/0167-6377(82)90021-9 |
| [16] | LAWLER E. L., Journal of Associated Computing Machinery 25 pp 612– (1978) |
| [17] | DOI: 10.1287/opre.35.4.556 · doi:10.1287/opre.35.4.556 |
| [18] | DOI: 10.1016/0167-6377(94)90026-4 · Zbl 0812.90066 · doi:10.1016/0167-6377(94)90026-4 |
| [19] | DOI: 10.1080/00207549008942855 · Zbl 0707.90054 · doi:10.1080/00207549008942855 |
| [20] | LIOU , J. and SMITH , M. L. 1992 , Scheduling flowshop with limited in-process wait . Research report , Texas Technology University , Lubbock . |
| [21] | DOI: 10.1080/00207549308956713 · doi:10.1080/00207549308956713 |
| [22] | DOI: 10.1111/j.1540-5915.1987.tb01520.x · doi:10.1111/j.1540-5915.1987.tb01520.x |
| [23] | DOI: 10.1080/00207548408942479 · doi:10.1080/00207548408942479 |
| [24] | DOI: 10.1287/mnsc.6.1.1 · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1 |
| [25] | DOI: 10.1016/0305-0483(83)90088-9 · doi:10.1016/0305-0483(83)90088-9 |
| [26] | DOI: 10.1080/00207548408942436 · Zbl 0541.90055 · doi:10.1080/00207548408942436 |
| [27] | PROUST C., Proceedings of the Summer School on Scheduling pp 297– (1992) |
| [28] | DOI: 10.1080/00207549408957083 · Zbl 0904.90076 · doi:10.1080/00207549408957083 |
| [29] | DOI: 10.1016/0377-2217(93)90248-L · Zbl 0803.90078 · doi:10.1016/0377-2217(93)90248-L |
| [30] | DOI: 10.1016/0377-2217(89)90208-7 · Zbl 0691.90038 · doi:10.1016/0377-2217(89)90208-7 |
| [31] | DOI: 10.1016/0377-2217(90)90090-X · Zbl 0702.90043 · doi:10.1016/0377-2217(90)90090-X |
| [32] | DOI: 10.1287/mnsc.23.9.1016 · Zbl 0367.90077 · doi:10.1287/mnsc.23.9.1016 |
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.
