%0 Journal Article
%T Minimizing the Number of Tardy Jobs on a Single Machine with an Availability Constraint
%A Ehsan Molaee
%A Ghasem Moslehi
%J Journal of Industrial Engineering
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/568317
%X 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
%U http://www.hindawi.com/journals/jie/2014/568317/