مقاله سال ۲۰۱۷

 مجله امگا – Omega

Contemporary production and service systems often operate in a dynamic and uncertain environment, in which unexpected events may occur from time to time. Should the expected events be disruptions, they may cause some resources (machines or facilities) to be unavailable for a certain period of time, which will directly affect the utilization of the resources and ultimately customer service. Examples of disruptive events occurring during production abound, e.g., machine breakdowns, power failures, and shortages of raw materials, personnel, tools, etc. Research on scheduling that takes disruptions into account is commonly known as scheduling with availability constraints, which has been extensively investigated in the literature. Lee et al. [13], Sanlaville and Schmidt [23], Schmidt [25], and Ma et al. [19] survey and summarize the major results and practices in this area.

Machine scheduling with availability constraints can be categorized into two major classes. One class is where the machine unavailability is deterministic due to some internal factors such as preventive maintenance. In this case, both the disruption starting time and duration are either fixed in advance [4,8–۱۱,۲۰,۳۱,۳۴,۳۳] or are decision variables in the scheduling model [5,18,21,22,28–۳۰,۳۲]. The other class is where the machine unavailability is stochastic [1–۳], which is caused by machine breakdowns or other internal and external factors. Lee and Yu [15] consider single-machine scheduling with potential disruptions due to external factors, e.g., bad weather (typhoons and snowstorms), labour strikes, power shortages, etc. In such a case, the disruption starting time is roughly known (should it happen); however, the disruption duration is unknown until the damage is made. They provide pseudo-polynomial-time algorithms to solve the problems of minimizing the expected total weighted completion time and the expected maximum tardiness. Subsequently, Lee and Yu [16] extend the results to the parallel-machine case to minimize the expected total weighted completion time.

We pursue the stream of research initiated by Lee and Yu [15,16]. We consider scheduling of jobs on m identical parallel machines that are subject to potential disruptions in a deteriorating production environment, which means that the job processing times will deteriorate over time. Some of the machines may become unavailable for a period of time over the scheduling period due to potential disruptions arising from worker shortage, power shortage, etc. In such a case, we often know the disruption starting time (should it happen) in advance, yet the duration is unknown until it happens. That is, there is a possibility that a disruption will happen at a particular time and the disruption will last for a certain duration with a certain probability. So the machine unavailability will only be revealed at the time when the disruption occurs. Thus we assume that once a disruption occurs, we will know its duration. Specifically, we consider two cases. One is to perform maintenance immediately on each of the disrupted machines when a disruption occurs and the other is not to perform machine maintenance, where performing machine maintenance will improve the efficiency of the machine by returning it to its original state of efficiency at the expense of the cost incurred from maintenance. With known probabilities of all the unexpected events, the scheduling objective is to find an optimal schedule for the jobs to minimize the expected total completion time of the jobs. We extend the work of Lee and Yu [16] in three major ways as follows:
We consider the scheduling problem in a deteriorating production environment, i.e., the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging, which more accurately reflects real-life production.
We assume that machine unavailability will only occur on some of the machines, which is the case where the factory has backup power to keep some of the machines working when the disruption occurs due to power shortage, whereas Lee and Yu [16] assume that machine unavailability will happen on all the machines.
We include the case where the disruption may not happen (i.e., ζγ ¼ ۰) in the non-resumable case, which Lee and Yu [16] do not consider.