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: Scheduling, makespan, Open shop, deteriorating jobs,

Abstract :

This manuscript examines the two-machine open shop scheduling problem where the latter a job is scheduled the longer it takes to process this job. The performance is measured by minimizing the makespan. By modifying existing algorithms for the corresponding problem with fixed processing times, two new algorithms are developed for the problem under consideration. The proofs of optimality of both algorithms are presented. The execution of these algorithms is illustrated by two numerical examples. Finally, both algorithms are further modified to solve a more generalized problem where the time demanded to process a job is a general linear function of its beginning time.

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