A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints
Tóm tắt
In this paper, we develop a polynomial-time approximation scheme for the two-machine flow shop scheduling problem with several availability constraints on the first machine, under the resumable scenario.
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)
Floudas C.A., Pardalos P.M.: Encyclopedia of optimization. 2nd edn. Springer, Berlin (2009)
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). doi:10.1007/s11590-009-0137-6
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). doi:10.1007/s10288-010-0119-7
Hadda H., Dridi N., Hajri-Gabouj S.: An improved heuristic for two-machine flow shop scheduling with an avilability constraint and nonresumable jobs. 4OR-Q. J. Oper. Res. 8, 87–99 (2010). doi:10.1007/s10288-009-0102-3
Johnson S.M.: Optimal two- and three-stage production schedules with setup times included. Res. Log. Q. 1, 61–68 (1954)
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)
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)
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)
Ng C.T., Kovalyov M.Y.: An FPTAS for scheduling a two-machine flowshop with one unavailability interval. Nav. Res. Log. 51, 307–315 (2004)
Ying M., Chengbin C., Chunrong Z.: A survey of scheduling with deterministic machine availability constraints. Comput. Ind. Eng. 58, 199–211 (2010)