In this paper, we present a prediction based iterative decomposition algorithm for solving large-scale job shop scheduling problems using the rolling horizon scheme and the prediction mechanism, in which the original large-scale scheduling problem is iteratively decomposed into several sub-problems. In the proposed algorithm, based on the job-clustering method, we construct the Global Scheduling Characteristics Prediction Model (GSCPM) to obtain the scheduling characteristics values, including the information of the bottleneck jobs and the predicted value of the global scheduling objective. Then, we adopt the above scheduling characteristics values to guide and coordinate the process of the problem decomposition and the sub-problem solving. Furthermore, we propose an adaptive genetic algorithm to solve each sub-problem. Numerical computational results show that the proposed algorithm is effective for large-scale scheduling problems.
The job shop scheduling problem is one of the most complicated combinatorial optimization problems [1], [2] and [3], and it has long been a significant research field since Akers and Jackson [4] and [5] proposed some efficient methods for 2×m2×m and n×2n×2 job shop scheduling problems. From then on, many effective exact methods, including mathematical programming methods [6], [7] and [8], etc., have been proposed to solve job shop scheduling problems with smaller scale. Since the job shop scheduling problem is a kind of typical NP-hard problem, the above exact methods are not suitable for solving job shop scheduling problems with larger scale. The dispatching rules [9] and [10] and the near-optimal methods, such as the genetic algorithm [11], [12] and [13], tabu search [14], [15] and [16] and simulated annealing [17], [18] and [19], have become very popular and have gained much success in solving job shop scheduling problems with larger scale. However, in practical manufacturing environments the scale of job shop scheduling problems could be much larger; for example, in some big textile factories, the number of jobs may be up to 1000. For large-scale scheduling problems, the performances of the above scheduling methods, including exact methods, dispatching rules and near-optimal methods, are not very satisfactory.
Decomposition based scheduling methods have long been effective and popular in handling larger-scale scheduling problems [20], [21], [22], [23], [24], [25], [26] and [27]. One of the key points in applying the above decomposition methods to solve large-scale scheduling problems is how to evaluate globally a given schedule of each sub-problem. Traditional decomposition based methods in the literature, such as shifting bottleneck procedures [21], rolling horizon based methods [27] and graph decomposition based methods [24], evaluate a given schedule of the sub-problem using either some local scheduling indices or the lower/upper bound of the global scheduling objective. However, for large-scale job shop scheduling problems, the performance of decomposition algorithms based on the above two evaluation methods is usually not satisfactory because the local scheduling indices or the bounds of the global scheduling objective cannot reflect the global characteristics effectively in most cases.
In this paper, aiming at solving large-scale job shop scheduling problems with the objective of minimizing the total tardiness, we propose a prediction based iterative decomposition algorithm (PIDA). In the PIDA, the original scheduling problem is iteratively decomposed into several sub-problems, each of which corresponds to a time window respectively, and each sub-problem is iteratively defined and solved with the rolling horizon scheme and the prediction mechanism. In the course of defining and solving each sub-problem, we first construct the Global Scheduling Characteristics Prediction Model (GSCPM) to obtain the scheduling characteristics values for guiding and coordinating the process of the problem decomposition and the sub-problem solving in order that the global scheduling performance can be improved. Then, an adaptive genetic algorithm based on the GSCPM is proposed to solve the current sub-problem, and the partial scheduling policy corresponding to the current sub-problem solved is fixed. After that, the next sub-problem will be defined and solved according to the above procedure until all the sub-problems are solved. Finally, an overall schedule which is composed of all the fixed partial scheduling policies of the sub-problems can be obtained.
The main difference between traditional rolling horizon based decomposition algorithms (take the RHA (Rolling Horizon Algorithm) proposed by Marcos Singer [27] as an example) and the proposed PIDA can be illustrated in three aspects: (1) in the RHA, all the sub-problems have been defined before the first sub-problem is solved, while in the PIDA, we define the current sub-problem only after the former sub-problem is already solved; (2) in the RHA, the schedule of each sub-problem is evaluated by a lower bound of the global scheduling objective value, while in the PIDA, we evaluate the schedule of each sub-problem by the predicted value of the global scheduling objective; (3) in the RHA, each sub-problem is solved by a modified shifting bottleneck heuristic, which has an exponential computational complexity, while in the PIDA, we solve each sub-problem with an adaptive genetic algorithm based on the GSCPM.
Numerical computational results on large-scale job shop scheduling problem instances up to 1000 jobs and 20 machines indicate that the PIDA is effective and outperforms the RHA and some efficient dispatching rules (EDD/SLK/MDD). Also, the results of this paper are promising for large-scale job shop scheduling problems with due-date-related objectives in practical manufacturing environments.
This paper is organized as follows. Problem formulation is given in Section 2. Section 3 describes the detailed PIDA. Numerical computations are made in Section 4. Finally, conclusions are drawn in Section 5.
In this paper, a prediction based iterative decomposition algorithm for solving large-scale job shop scheduling problem is proposed. In this algorithm, the original large-scale problem is decomposed into several sub-problems, and each sub-problem is iteratively defined and solved with the rolling horizon scheme and the prediction mechanism. Numerical computational results show that PIDA is effective for large-scale scheduling problems. The results of this paper are promising for optimizing large-scale due-date-related objective based scheduling problems in practical manufacturing environments.
