The Two-stage Assembly Flow Shop Scheduling with an Availability Constraint: Worst Case Analysis
Tóm tắt
In this paper, we are interested in handling the limited availability of machines in the two-stage assembly flow shop scheduling problems. Emphasis is put on the semiresumable case with respect to the minimization of the makespan. We provide, when possible, heuristics with a tight worst-case ratio bound of 2.
Tài liệu tham khảo
Breit, J.: An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. Inf. Process. Lett. 90, 273–278 (2004)
Cheng, T.C.E, Wang, G.: An improved heuristic for two-machine flowshop scheduling with an availability constraint. Oper. Res. Lett. 26, 223–229 (2000)
Hadda, H., Dridi, N., Hajri-Gabouj, S.: The two-stage assembly flow shop scheduling with an availability constraint. In: Proc. 3rd Multidisciplinary International Conference on Scheduling: Theory and Application, pp. 184–191. Paris, France (2007)
Hadda, H., Dridi, N., Hajri-Gabouj, S.: An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs. 4OR-Q. J. Oper. Res. 8, 87–99 (2010)
Hadda, H.: A (\(\frac 4 3 \))-approximation algorithm for a special case of the two machine flow shop problem with several availability constraints. Optim. Lett. 3, 583–592 (2009)
Hadda, H.: An improved algorithm for the two machine flow shop problem with several availability constraints. 4OR-Q. J. Oper. Res. 8, 271–280 (2010)
Hadda, H.: A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints. Optim. Lett. 6, 559–569 (2012)
Haouari, M., Daouas, T.: Optimal scheduling of the 3-machine assembly-type flow shop. RAIRO Oper. Res. 33, 439–445 (1999)
Hariri, A.M.A., Potts, C.N.: A branch and bound algorithm for the two-stage assembly scheduling problem. Eur. J. Oper. Res. 103, 547–556 (1997)
Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist. Quart. 1, 61–68 (1954)
Kubiak, W., Blazewicz, J., Formanowicz, P., Breit, J., Schmidt, G.: Two-machine flow shops with limited machine availability. Eur. J. Oper. Res. 136, 528–540 (2002)
Kubzin, M.A., Potts, C.N., Strusevich, V.A.: Approximation results for flow shop scheduling problems with machine availability constraints. Comput. Oper. Res. 36, 379–390 (2009)
Lee, C.Y.: Minimizing the makespan in the two-machine flow shop scheduling problem with an availability constraint. Oper. Res. Lett. 20, 129–139 (1997)
Lee, C.Y., Two-machine flowshop scheduling with availability constraints. Eur. J. Oper. Res. 114, 420–429 (1999)
Lee, C.Y., Cheng, T.C.E., Lin, B.M.T.: Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Manag. Sci. 39, 616–625 (1993)
Ng, C.T., Kovalyov, M.Y.: An FPTAS for shceduling a two-machine flowshop with one availability interval. Nav. Res. Logist. 51, 307–315 (2004)
Potts, C.N., Sevast’janov, S.V., Strusevich, V.A., Van wassenhove, L.N., Zwaneveld, C.M.: The two-stage assembly scheduling problem: complexity and approximation. Oper. Res. 43, 346–355 (1995)
Ying, M., Chengbin, C., Chunrong, Z.: A survey of scheduling with deterministic machine availability constraints. Comput. Ind. Eng. 58, 199–211 (2010)