Two-Machine Open Shop Scheduling with Proportionally Deteriorating Jobs and Makespan Objective

Subject Areas : Business and Marketing

Ching-Fang Liaw ¹

1 - Department of Industrial Engineering and Management, Chaoyang University of Technology, Taichung, Taiwan

Received: 2022-01-07 Accepted : 2022-08-17 Published : 2022-09-01

Keywords:

References:

Abreu, L.R., Prata, B.A., Framinan, J.M. & Nagano, M.S. (2022). New efficient heuristics for scheduling open shops with makespan minimization. Computers & Operations Research, 142 (2022) 105744. doi.:10.1016/j.cor.2022.105744.

Adiri, I. & Amit, N. (1983). Route-dependent open-shop scheduling. IIE Transactions, 15(3), 231-234.

Ahmadian, M.M., Khatami, M., Salehipour, A. & Cheng, T.C.E. (2021). Four decades of research on the open-shop scheduling problem to minimize the makespan. European Journal of Operational Research, 295, 399-426.

Alidaee, B. & Womer, N.K. (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society, 50, 711–720.

Behnamian, J. (2019). Diversified Particle Swarm Optimization for Hybrid Flowshop Scheduling. Journal of Optimization in Industrial Engineering, 12(2), 107- 119. doi: 10.22094/JOIE.2018.671.1433.

Breit, J., Schmidt, G. & Strusevich, V.A. (2001). Two-machine open shop scheduling with an availability constraint. Operations Research Letters, 29, 65-77.

Cheng, T.C.E. & Sharkhlevich, N,V. (2007). Two-machine open shop problem with controllable processing times. Discrete Optimization, 4, 175-184.

Cheng, T.C.E., Ding, Q. & Lin, B.M.-T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13.

Chernykh, I., Kononov, A. & Sevastyanov, S. (2013). Efficient approximation algorithms for the routing open shop problem. Computers and Operations Research, 40(3), 841-847.

de Werra, D. (1989). Graph-theoretical models for preemptive scheduling. Advances in Project Scheduling (p171-185). Elsevier, Amsterdam, Netherlands.

Enayati, M., Asadi-Gangraj E. & Paydar, M.M. (2021). Scheduling on Flexible Flow Shop with Cost-related Objective Function Considering Outsourcing Options. Journal of Optimization in Industrial Engineering, 14(2), 53-72. doi: 10.22094/JOIE.2020.1873983.1674

Gawiejnowicz, S. & Kolinska, M. (2021). Two- and three-machine open shop scheduling using LAPT-like rules. Computers & Industrial Engineering, 157, (2021) 107261. doi: 10.1016/j.cie.2021.107261.

Gawiejnowicz, S. (1996a). A note on scheduling on a single processor with speed dependent on a number of executed jobs. Information Processing Letters, 57, 297–300.

Gawiejnowicz, S. (1996b). Brief survey of continuous models of scheduling.  Foundations of Computing and Decision Sciences, 21, 81–100.

Gawiejnowicz, S. (2020a). A review of four decades of time-dependent scheduling: main results, new topics and open problems. Journal of Scheduling, 23, 3-47.

Gawiejnowicz, S. (2020b). Models and algorithms of time-dependent scheduling. Springer, Berlin-Heidelberg, Germany. doi:10.1007/978-3-662-59362-2.

Gawiejnowicz, S. (2008). Time-dependent scheduling. Springer, Berlin, Germany.

Gonzalez, T. & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23, 665-679.

Graham, R.L., Lawler, E.L., Lenstra, J.K. & Rinnooy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287-326.

Gribkovskaia, I.V., Lee, C.-Y., Strusevich, V.A. & de Werra, D. (2006). Three is easy, two is hard: open shop sum-batch scheduling problem refined. Operations Research Letters, 34, 459-464.

Huang, Z., Zhuang, Z., Cao, Q., Lu, Z., Guo, L. & Qin, W. (2019). A survey of intelligent algorithms for open shop scheduling problem. Procedia CIRP 83 (2019) 569–574.

Khramova, A.P. & Chernykh, I. (2021). A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing. Journal of Scheduling, 24, 405–412. doi:10.1007/s10951-021-00694-7.

Kononov, A. & Gawiejnowicz, S. (2001). NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operations Research Society, 52, 708-718.

Kononov, A. (1996). Combinatorial complexity of scheduling jobs with simple linear deterioration. Discrete Analysis and Operations Research, 3, 15-32. (In Russian)

Kononov, A. (1998). Single machine scheduling problems with processing times proportional to an arbitrary function. Discrete Analysis and Operations Research, 5, 17-37. (In Russian)

Kubiak, W. (2022). A book of Open Shop Scheduling: Algorithms, Complexity and Applications. Springer Nature, Berlin, Germany. doi:10.1007/978-3-030-91025-9.

Li, S.-S. (2011). Scheduling proportionally deteriorating jobs in two-machine open shop with a non-bottleneck machine. Asia-Pacific Journal of Operations Research, 28, 623-631.

Mejía G. & Yuraszeck, F. (2020). A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with

travel/setup times.  European Journal of Operational Research, 285, 484-496.

Mosheiov, G. (2002). Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 117, 195-209.

Mosheiov, G., Sarig, A., Strusevich, V.A. & Mosheiff, J. (2018). Two-machine flow shop and open shop scheduling problems with a single maintenance window. European Journal of Operational Research, 271, 388-400.

Pinedo, M. & Schrage, L. (1982). Stochastic shop scheduling: A survey. Deterministic and Stochastic Scheduling (p181-196). Springer, Berlin, Germany.

Soper, A.J. (2015). A cyclical search for the two machine flow shop and open shop to minimise finishing time. Journal of Scheduling, 18(3), 311-314.

Strusevich, V.A. & Rustogi, K. (2017). Scheduling with time-changing effects and rate-modifying activities. Springer, Berlin, Germany.

Strusevich, V.A., Van De Waart, A. & Dekker, R. (1999). A 3/2 algorithm for two-machine open shop with route-dependent processing times. Journal of Heuristics, 5(1), 5-28.

Strusevich, V.A. (2022). Complexity and approximation of open shop scheduling to minimize the makespan: A review of models and approaches. Computers & Operations Research, 144 (2022) 105732. doi: 10.1016/j.cor.2022.105732.

Tellache, N.E., Boudhar, M. & Yalaoui, F. (2019). Two-machine open shop problem with agreement graph. Theoretical Computer Science, 796, 154-168.

Yavari, S., Azab, A., Baki, M.F., Alcelay, M. & Britt, J. (2020). Machine Scheduling for Multitask Machining. Journal of Optimization in Industrial Engineering, 13(2), 1-15. doi: 10.22094/JOIE.2020.1869865.1660