Most scheduling problems are based on the assumption that machines work continuously during the planning horizon. This assumption is not true in many production environments because the machine may not be available during one or more periods such as during breakdowns or maintenance operations. In this paper, the problem of the single machine scheduling with one unavailability period and nonresumable jobs with the aim of minimizing the number of tardy jobs is studied. A number of theorems are proved and a heuristic procedure is developed to solve the problem. A branch-and-bound approach is also presented which includes upper and lower bounds and efficient dominance rules. Computational results for 2680 problem instances show that the branch-and-bound approach is capable of solving 98.7% of the instances optimally, bearing witness to the efficiency of the proposed procedure. Our results also indicate that the proposed approaches are more efficient when compared to other methods. 1. Introduction Most scheduling problems take the fact that the machine works continuously during the planning horizon for granted. This assumption may be unrealistic in many production environments as the machine becomes unavailable during breakdowns or maintenance operations. The number of tardy jobs is one of the important objective functions in scheduling problems. This target has wide applications in many production and service environments and reflects factors of external cost based on due dates such as customer satisfaction. The number of tardy jobs can represent orders of customers that are not satisfied. In this paper, the single machine scheduling problem with a known unavailability period and nonresumable jobs with the objective of minimizing the number of tardy jobs is considered. According to Pinedo [1] separation, this problem is denoted by . So far, a few researchers have studied single machine problems with availability constraints. In these problems, there are three general states for jobs including resumable, nonresumable, and semiresumable states. According to the resumable scenario, job preemption is allowed. This means that if a job cannot be finished before a nonavailability period of the machine, its processing can be resumed when the machine is available again. According to the nonresumable scenario, preemption is undesirable and the whole processing of the job should be repeated if it cannot be finished before the unavailability period. In the semiresumable state, part of the processing should be repeated if it cannot be finished before the nonavailability
References
[1]
M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice Hall, New Jersey, NJ, USA, 2002.
[2]
C.-Y. Lee, “Machine scheduling with an availability constraint,” Journal of Global Optimization, vol. 9, no. 3-4, pp. 395–416, 1996.
[3]
J. B. Sidney, “An extension of Moore's due date algorithm,” in Symposium on the Theory of Scheduling and Its Applications, S. E. Elmaghrebi, Ed., Lecture Notes in Economics and Mathematical Systems, pp. 393–398, Springer, New York, NY, USA, 1973.
[4]
I. Adiri, J. Bruno, E. Frostig, and A. H. G. Rinnooy Kan, “Single machine flow-time scheduling with a single breakdown,” Acta Informatica, vol. 26, no. 7, pp. 679–696, 1989.
[5]
C. Y. Lee and S. D. Liman, “Single machine flow-time scheduling with scheduled maintenance,” Acta Informatica, vol. 29, no. 4, pp. 375–382, 1992.
[6]
C. Sadfi, B. Penz, C. Rapine, J. Blazewicz, and P. Formanowicz, “An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints,” European Journal of Operational Research, vol. 161, no. 1, pp. 3–10, 2005.
[7]
J. Breit, “Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint,” European Journal of Operational Research, vol. 183, no. 2, pp. 516–524, 2007.
[8]
I. Kacem and C. Chu, “Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint,” International Journal of Production Economics, vol. 112, no. 1, pp. 138–150, 2008.
[9]
I. Kacem, “Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval,” Computers & Industrial Engineering, vol. 54, no. 3, pp. 401–410, 2008.
[10]
I. Kacem, C. Chu, and A. Souissi, “Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times,” Computers & Operations Research, vol. 35, no. 3, pp. 827–844, 2008.
[11]
C. J. Liao and W. J. Chen, “Single-machine scheduling with periodic maintenance and nonresumable jobs,” Computers and Operations Research, vol. 30, no. 9, pp. 1335–1347, 2003.
[12]
M. Ji, Y. He, and T. C. E. Cheng, “Single-machine scheduling with periodic maintenance to minimize makespan,” Computers and Operations Research, vol. 34, no. 6, pp. 1764–1770, 2007.
[13]
W.-J. Chen, “An efficient algorithm for scheduling jobs on a machine with periodic maintenance,” International Journal of Advanced Manufacturing Technology, vol. 34, no. 11-12, pp. 1173–1182, 2007.
[14]
I. Adiri, E. Frostig, and A. H. G. Rinnooy Kan, “Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs,” Naval Research Logistics, vol. 38, no. 2, pp. 261–271, 1991.
[15]
W.-J. Chen, “Minimizing number of tardy jobs on a single machine subject to periodic maintenance,” Omega, vol. 37, no. 3, pp. 591–599, 2009.
