AbstractThe single machine scheduling problem with variable maintenance has been widely investigated by both academics and practitioners. Differently from most papers proposed so far, and conforming to a real-world process in the semiconductor industry, in this paper a single variable maintenance task has to be carried out within a specific time interval. The maintenance duration is an increasing function of its starting time. The objective is to minimize the total tardiness considering release times and sequence dependent setup times of jobs as well. Since an earlier maintenance starting time implies a smaller maintenance duration but a higher completion time of the subsequent jobs, the best schedule including maintenance activity and jobs has to be achieved. In order to optimally solve the scheduling problem at hand, two distinct mixed integers linear programming models (MILPs) are proposed and compared under the computational efficiency viewpoint.
Allahverdi A, Aydilek H and Aydilek A. No-wait flowshop scheduling problem with two criteria; total tardiness and makespan. European Journal of Operational Research 2018; 269(2): 590-601. https://doi.org/10.1016/j.ejor.2017.11.070
Baker K. R and Trietsch D. Principles of sequencing and scheduling. John Wiley & Sons 2013.
Chen JS. Optimization models for the machine scheduling problem with a single flexible maintenance activity. Engineering Optimization 2006; 38(1): 53-71. https://doi.org/10.1080/03052150500270594
Cui WW, and Lu Z. Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates. Computers & Operations Research 2017; 80: 11-22. https://doi.org/10.1016/j.cor.2016.11.008
Graham RL, Lawler EL, Lenstra JK, and Kan AR. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics 1979; 5: pp. 287-326 Elsevier. https://doi.org/10.1016/S0167-5060(08)70356-X
Kubzin MA & Strusevich VA. Planning machine maintenance in two-machine shop scheduling. Operations Research 2006; 54(4): 789-800. https://doi.org/10.1287/opre.1060.0301
Luo W, Chen L & Zhang G. Approximation algorithms for scheduling with a variable machine maintenance. In International Conference on Algorithmic Applications in Management 2010; (pp. 209-219). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14355-7_22
Luo W, Cheng TE & Ji, M. Single-machine scheduling with a variable maintenance activity. Computers & Industrial Engineering 2015; 79: 168-174. https://doi.org/10.1016/j.cie.2014.11.002
Ma Y, Chu C, & Zuo C. A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 2010; 58(2): 199-211. https://doi.org/10.1016/j.cie.2009.04.014
Mosheiov G, & Sidney JB. Scheduling a deteriorating maintenance activity on a single machine. Journal of the Operational Research Society 2010; 61(5): 882-887. https://doi.org/10.1057/jors.2009.5
Pang J, Zhou H, Tsai YC & Chou FD. A scatter simulated annealing algorithm for the bi-objective scheduling problem for the wet station of semiconductor manufacturing. Computers & Industrial Engineering 2018; 123: 54-66. https://doi.org/10.1016/j.cie.2018.06.017
Schmidt G. Scheduling with limited machine availability. European Journal of Operational Research 2000; 121(1): 1- 15. https://doi.org/10.1016/S0377-2217(98)00367-1
Wang Q, Liu A & Xiao J. On exact algorithms for singlemachine scheduling problems with a variable maintenance. Computers & Industrial Engineering 2017; 107: 276-279. https://doi.org/10.1016/j.cie.2017.03.024
Xu D, Yin, Y & Li H. Scheduling jobs under increasing linear machine maintenance time. Journal of scheduling 2010; 13(4): 443-449. https://doi.org/10.1007/s10951-010-0182-0
Xu D, Wan L, Liu A, & Yang DL. Single machine total completion time scheduling problem with workloaddependent maintenance duration. Omega 2015; 52: 101-106. https://doi.org/10.1016/j.omega.2014.11.002