MILP Models for Scheduling Dynamic Jobs with Sequence Dependent Setup Times and a Variable Maintenance on a Single Machine


Mathematical programming, Sequencing, Global optimization, maintenance, Manufacturing.

How to Cite

Costa Antonio, Corsini Roberto, Cappadonna F. Antonio, & Fichera Sergio. (2018). MILP Models for Scheduling Dynamic Jobs with Sequence Dependent Setup Times and a Variable Maintenance on a Single Machine. Journal of Advances in Applied &Amp; Computational Mathematics, 5, 29–36.


 The 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.

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.

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.

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.

Kubzin MA & Strusevich VA. Planning machine maintenance in two-machine shop scheduling. Operations Research 2006; 54(4): 789-800.

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.

Luo W, Cheng TE & Ji, M. Single-machine scheduling with a variable maintenance activity. Computers & Industrial Engineering 2015; 79: 168-174.

Ma Y, Chu C, & Zuo C. A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 2010; 58(2): 199-211.

Mosheiov G, & Sidney JB. Scheduling a deteriorating maintenance activity on a single machine. Journal of the Operational Research Society 2010; 61(5): 882-887.

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.

Schmidt G. Scheduling with limited machine availability. European Journal of Operational Research 2000; 121(1): 1- 15.

Wang Q, Liu A & Xiao J. On exact algorithms for singlemachine scheduling problems with a variable maintenance. Computers & Industrial Engineering 2017; 107: 276-279.

Xu D, Yin, Y & Li H. Scheduling jobs under increasing linear machine maintenance time. Journal of scheduling 2010; 13(4): 443-449.

Xu D, Wan L, Liu A, & Yang DL. Single machine total completion time scheduling problem with workloaddependent maintenance duration. Omega 2015; 52: 101-106.