یک الگوریتم بازپخت شبیه سازی ترکیبی ایمنی برای مشکل زمان بندی تولید کارگاهی

A hybrid simulated annealing algorithm based on a novel immune mechanism is proposed for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The proposed immune procedure is built on the following fundamental idea: the bottleneck jobs existing in each scheduling instance generally constitute the key factors in the attempt to improve the quality of final schedules, and thus, the sequencing of these jobs needs more intensive optimization. To quantitatively describe the bottleneck job distribution, we design a fuzzy inference system for evaluating the bottleneck level (i.e. the criticality) of each job. By combining the immune procedure with a simulated annealing algorithm, we design a hybrid optimization algorithm which is subsequently tested on a number of job shop instances. Computational results for different-sized instances show that the proposed hybrid algorithm performs effectively and converges fast to satisfactory solutions.

The job shop scheduling problem (JSSP) has been an important research focus in both theoretical and industrial fields ever since the 1950s. Concerning its difficulty, JSSP was shown to be View the MathML sourceNP-hard in the strong sense [18]. Therefore, it is dramatically difficult to find the absolutely optimal solution even for very small instances. Actually, the well-known JSSP benchmark problem labeled as “FT10” or “MT10” which contains only 10 jobs and 10 machines was not solved to optimality until two decades after the problem was initially constructed [1]. After recognizing the remarkable difficulty of JSSP and the poor performance of exact solution methods, a lot of researchers now put their effort into meta-heuristic and local search optimization strategies for solving JSSP, such as simulated annealing (SA) [15], [27] and [3], genetic algorithm (GA) [28] and [7], tabu search (TS) [20], scatter search (SS) [8] and [25], particle swarm optimization (PSO) [26] and [17] and ant colony optimization (ACO) [5] and [11]. These intelligent optimization algorithms are relatively easy to implement and they could conveniently be adapted for different kinds of scheduling problems. This has made the research on them increasingly popular in the recent years. However, the converging processes of the standard versions of these algorithms tend to be too slow for practical-scale JSSPs. Specifically, in order to find satisfactory solutions, standard SA needs to start with a sufficiently high initial temperature and the cooling process must be slow enough. Only in this way can it be guaranteed that a large enough number of samples are obtained from the whole search space. Likewise, standard GA should employ a reasonably large population and an adequately long evolution process in order to produce enough offspring individuals. Under such a situation, it would be not difficult to observe a severe decline of the performance of these algorithms when they face larger scale JSSP instances. Because of the View the MathML sourceNP-hard nature of JSSP, the solution space will expand exponentially with the problem size. Finally, the actual limit on the available computational time and the memory size determines that the performance of heuristic local search methods alone will be unsatisfactory. To make the algorithms more powerful, two major sorts of approaches have been adopted and reported in the existing literature: (1) Great effort has been devoted to the modification and improvement of the local search algorithm itself, independently of the specific characteristics of the pending optimization problem. For example, the probabilistic model-building genetic algorithms (PMBGA) [22] and [29] produce new individuals by estimating the probability distribution of a selected set of high-quality solutions. This procedure actually replaces the conventional crossover and mutation operators in GA. Also remarkably, many hybrid algorithms have been devised in an attempt to combine the merits of two different local search methods. For example, the genetic local search algorithm presented in [4] makes use of the exploration ability of GA and the exploitation ability of iterated local search (ILS). (2) Due to the famous “No Free Lunch Theorem” (NFLT) [31] and much recent literature, researchers have gradually realized the importance of mining and utilizing problem-specific or instance-specific information during the optimization process of local search algorithms for hard problems. For example, the shifting bottleneck (SB) heuristic is based on the critical path theory for JSSP with makespan criterion. SB is therefore combined with GA in [6] in order to provide guidance for the searching process of GA. Moreover, the problem knowledge can also be introduced into the initial solution or the initial population, such as in [30], which also proves efficient in accelerating the convergence. The former approach is apparently independent of problem types, and therefore, such improvement can be directly applied to any optimization problem. However, in the latest research, the latter approach which is built on specific problem characteristics proves to be more successful for scheduling problems. The immune mechanism designed in this work also belongs to the latter approach because immunity is used to embed problem-specific knowledge into the general optimization process. Among the numerous studies for JSSP, the concept of “bottleneck” has been regarded as a significant type of characteristic information that could be utilized to generate promising solutions [10], [19] and [34]. In this paper, “bottleneck jobs” refer to those jobs whose processing sequence can have an obvious impact on the quality of final schedules. For most scheduling instances, the ultimate scheduling performance could be remarkably improved if these bottleneck jobs have been wisely scheduled. However, how to correctly identify the bottleneck level of each job under different scheduling objectives and in different optimization stages still belong to the unsolved problems which are currently under study in the scheduling community. In this research, we propose a new bottleneck job identification method which uses a fuzzy inference system to evaluate the bottleneck characteristic value for each job. Then, we design an immune mechanism based on the obtained bottleneck information for improving JSSP solutions. Finally, the immune mechanism is combined with SA to form a hybrid optimization algorithm called immune simulated annealing (ISA). In ISA, the simulated annealing mechanism is used to explore the solution space, while at the same time, the immune mechanism aims at producing high-quality solutions from the current solution. Computational results for problems of different sizes show that ISA is effective and robust. The rest of the paper is organized as follows. The discussed job shop scheduling problem is formulated in Section 2. Section 3 describes the immune algorithm for JSSP. Section 4 deals with the design and implementation of the hybrid ISA algorithm. The relevant computational results are provided in Section 5. Finally, some concluding remarks are given in Section 6.

In this paper, a hybrid immune simulated annealing algorithm is proposed for solving the job shop scheduling problem. The immune algorithm enhances the local search ability of SA by focusing more computational effort on the optimization of bottleneck jobs. Before applying the immune operator, the bottleneck levels of each job are evaluated by a fuzzy inference system based on scheduling knowledge. The defined bottleneck characteristic values could characterize the most crucial jobs at different stages of the optimization process. Finally, numerical computational results show that the proposed hybrid algorithm is effective and efficient for solving JSSP. Moreover, the algorithm is also promising for due date related scheduling problems in practical manufacturing environment. The future research can be conducted in the following aspects: (1) Consistent with the results from other literature, this paper also highlights the importance of incorporating problem-specific knowledge into the optimization algorithm. Now that this research covers a possible way of discovering “bottleneck” information using fuzzy inference system, it is worthwhile to investigate other methods for knowledge discovery (e.g. the data mining techniques) and other significant types of characteristic information in JSSP except for bottleneck (e.g. the distribution of solutions in the search space). (2) Artificial immune systems have caused wide attention in the recent years because of its convenient adaptability and intelligent learning feature. This paper proposes a novel immune mechanism based on bottleneck job adjustment. It is highly possible to develop other immunity-based mechanisms for combination with local search algorithms. For example, if the optimization objective is makespan, then the well-established constraint propagation theory [2] and [23] can be used to design an effective immune operator for use in SA or GA.