This paper addresses the makespan minimization in a job-shop environment where the machines are not available during the whole planning horizon. The disjunctive graph model is used to represent the schedules and the concept of blocks is generalized to include the unavailability periods of machines. To solve the problem, we develop a taboo thresholding heuristic that uses a new block-based neighborhood function. Some sufficient conditions to eliminate the evaluation of non-improving moves are proposed. Experiments performed on existing problem instances of the literature show the efficiency of the proposed heuristic.
Current trends in scheduling literature are toward integrating practical constraints in traditional scheduling models. One of these constraints that attracted researchers during the last decade is the unavailability of machines (Ma, Chu, & Zuo, 2010). In practice, machines are not available during the whole planning horizon because of breakdowns that may happen. Moreover, machines can be voluntarily stopped to perform some maintenance tasks such as washing or control operations.
The machine availability constraints encountered in production systems can either be fixed or non-fixed. In the fixed type, the starting times of unavailability periods (or holes) are known in advance while they are flexible in the second type and must be determined by the production scheduling procedure. The non-fixed type is generally used to implement preventive maintenances. Unavailability periods can also be classified depending on whether they allow or not the preemption of operations, i.e. resumable, semi-resumable or non-resumable (Lee, 1997 and Lee, 1999), non-preemptive (Aggoune & Portmann, 2006), crossable or non-crossable (Mauguière, Billaut, & Bouquard, 2005).
We investigate in this paper the fixed and non-preemptive unavailability periods in a job-shop environment with n jobs and m machines in order to minimize the makespan. Each job Ji consists of a linear sequence of m operations. Each machine Mk can perform at most one operation at a time and each operation x of job Ji needs one machine during px time-units. Several unavailability periods Hk,j = [lk,j, uk,j] may occur on each machine Mk, k = 1, … , m; j = 1, … , sk, where sk is the number of unavailability periods of machine Mk. The starting and finishing times of these periods are known in advance and fixed. Operations are strictly non-preemptive, which means that their execution can be interrupted neither by unavailability periods, nor by other operations.
This paper proposes a simple and efficient local search heuristic for the job-shop problem with availability constraints, based on known methods solving the classical job-shop problem. The remainder of the paper is organized as follows. Section 2 summarizes the previous studies on shop scheduling problems with machine availability. Section 3 first recalls the disjunctive graph model for representing the schedules and then presents some properties of this graph. The main contribution of the paper is presented in Section 4 in which a taboo thresholding procedure is proposed to solve the problem. Comparisons of the proposed heuristic with existing approaches are shown in Section 5. Section 6 concludes the paper and gives some research directions.
We have investigated in this paper the minimization of the makespan in a job-shop environment with limited machine availability. The concept of block is generalized to include the unavailability periods of machines, and a new neighborhood function is proposed. A taboo thresholding procedure that uses the new neighborhood function and some sufficient conditions to eliminate non-improving moves are developed. Experiments carried out on instances of the literature show the efficiency of the proposed algorithm. New instances are introduced as a starting point for further research on this problem. The proposed methodology points out several interesting avenues for future research. The first one is the extension of the taboo thresholding to solve non-max criteria. It will be also interesting to modify the proposed heuristic to take into account, in the same model, all possible cases for an operation to be interrupted or not by an unavailability period. Another interesting topic is the extension of the heuristic for solving the flexible job-shop problem with limited machine availability.
