Scheduling a two-stage hybrid flowshop with separable setup and removal times. (English) Zbl 0809.90080
Summary: This paper considers the two-stage flowshop scheduling problem where each stage consists of several identical parallel machines and the setup and removal times of each job at each stage are separated from the processing times. A polynomial optimization algorithm is developed for the special case where the first stage contains only one machine and the number of identical parallel machines at the second stage is equal to or greater than the total number of jobs. In view of the NP-completeness of this problem, four heuristic algorithms are developed for the case where there is one machine at stage 1 and the number of identical parallel machines at the second stage is less than the total number of jobs. The proposed heuristic algorithms are empirically tested to determine their effectiveness in finding an optimal schedule.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
two-stage flowshop scheduling; identical parallel machines; polynomial optimization algorithm; NP-completeness; heuristic algorithmsReferences:
| [1] | Baker, K. R., Scheduling groups of jobs in the two-machine flow shop, Mathematical and Computer Modelling, 13/3, 29-36 (1990) |
| [2] | Brah, S. A.; Hunsucker, J. L., Branch and bound algorithm for a flowshop with multiple processors, European Journal of Operational Research, 51/1, 88-99 (1991) · Zbl 0732.90040 |
| [3] | Brah, S.; Hunsucker, J.; Shah, J., Mathematical modeling of scheduling problems, Journal of Information and Optimization Sciences, 12/1, 113-137 (1991) · Zbl 0729.90052 |
| [4] | Deal, D. E.; Hunsucker, J. L., The two-stage flowshop scheduling problem with \(M\) machines at each stage, Journal of Information and Optimization Sciences, 12/3, 407-417 (1991) · Zbl 0825.90544 |
| [5] | Dileepan, P.; Sen, T., Job lateness in a two-machine flowshop with setup times separated, Computers & Operations Research, 18/6, 549-556 (1991) · Zbl 0747.90046 |
| [6] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guided Tour to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [7] | Gupta, J. N.D., A review of flowshop scheduling research, (Ritzman; etal., Disaggregation: Problems in Manufacturing and Service Organizations (1979), Martinus Nijhoff: Martinus Nijhoff The Hague), 363-388 |
| [8] | Gupta, J. N.D., Two-stage, hybrid flowshop scheduling problem, Journal of the Operational Research Society, 39/4, 359-364 (1988) · Zbl 0639.90049 |
| [9] | Gupta, J. N.D.; Tunc, E. A., Schedules for a two stage hybrid flowshop with parallel machines at the second stage, International Journal of Production Research, 29/7, 1489-1502 (1991) |
| [10] | Hunsucker, J. L.; Shah, J. R., Performance of priority rules in a due date flowshop, OMEGA, 20/1, 73-89 (1992) |
| [11] | Johnson, S. M., Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly, 1/1, 61-68 (1954) · Zbl 1349.90359 |
| [12] | Langston, M. A., Interstate transportation planning in the deterministic flowshop environment, Operations Research, 35/4, 556-564 (1987) |
| [13] | Proust, C.; Gupta, J. N.D.; Deschamps, V., Flowshop scheduling with set-up, processing and removal times separated, International Journal of Production Research, 29/3, 479-494 (1991) |
| [14] | Salvador, M. S., A Solution to a special class of flow shop scheduling problems, (Elmaghraby, S. E., Symposium of the Theory of Scheduling and Applications (1973), Springer-Verlag: Springer-Verlag New York), 83-91 · Zbl 0297.90036 |
| [15] | Sawik, T. J., Scheduling flowshops with parallel machines and finite in-process buffers by multilevel programming, (Iri, W. M.; Yajima, K., System Modelling and Optimization (1988), Springer-Verlag: Springer-Verlag Berlin), 691-700 |
| [16] | Sule, D. R., Sequencing \(n\) jobs on two machines with setup, processing and removal times separated, Naval Research Logistics Quarterly, 29/3, 517-519 (1982) · Zbl 0511.90073 |
| [17] | Szwarc, W.; Gupta, J. N.D., A Flow-shop with sequence-dependent additive setup times, Naval Research Logistics, 34/5, 619-627 (1987) · Zbl 0657.90046 |
| [18] | Zijm, W. H.M.; Nelissen, E. H.L. B., Scheduling a flexible machining centre, Engineering Costs and Production Economics, 19/1-3, 249-258 (1990) |
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.
