关键词: 单机调度, 可重入特征, 成组加工, 分布估计算法

Abstract: A single machine scheduling problem with re-entrant and group features is extracted from the realistic hot rolling production process of wide plates in the steel manufacturing industry. In this problem, jobs need to be processed in two processes, and a certain waiting time is needed between processes. To improve production efficiency, there is the possibility of group processing for adjacent jobs. This kind of scheduling problem with re-entrant and group features exists not only in the rolling shop of iron and steel industries, but also in other discrete manufacturing industries. However, to the best of our knowledge, no relevant research results have been found. Therefore, it is of great significance to study this scheduling problem.
This realistic production scheduling problem is first formulated as a mixed integer linear programming model with the goal of minimizing the makespan, which enables practitioners to solve small-scale instances using commercial solvers. Then it is proven that this problem is strongly NP-hard. Furthermore, and two key characteristics of the optimal solution are proved, which lays a solid foundation for the design of algorithm.
To efficiently solve this problem, an improved estimation of distributed algorithm (IEDA) is proposed according to the problem characteristics. Unlike other approaches of evolutionary algorithms, IEDA uses neither crossover nor mutation. It generates new offspring according to a probabilistic model learned from a population of parents. First, a problem-specific heuristic is presented to construct the initial population. Then, an effective probabilistic model is designed, where both the order of the job in the sequence and the similar blocks of jobs presented in the selected parents are taken into account. After that, local search procedures based on maximum reduction are designed to guide the IEDA to the promising regions at a fast speed. Finally, some individuals in the current population are replaced with new generated offspring. These steps are repeated until one stopping criterion is met.
The studied problem is NP-hard and can be solved efficiently by various algorithms. Although these algorithms might be effective, knowing a lower bound for the problem would enable us to assess how good they are. Therefore, two different lower bounds are developed so as to effectively evaluate the performance of the proposed IEDA. Both of these two lower bounds are based on mathematical analysis of the studied problem.
In the computational experiments, the best combination of parameters in the IEDA is first identified using the Taguchi method. Since no existing algorithm can be directly used, we select three state-of-the-art meta-heuristic algorithms developed for single machine scheduling problem. A lot of experiments are carried out, and the results show that the proposed IEDA can not only generate better solutions but also perform more steadily with various problem sizes. Therefore, we can conclude that the proposed IEDA is superior to the other three algorithms at solving the considered problem.
This work only studies the case where two jobs are processed in a group. In actual industrial production, there are three or more jobs that are processed in a group. In further research, we will study this as an object, and design a more efficient algorithm by mining scheduling rules based on problem characteristics.

Key words: single machine scheduling, re-entrant, group processing, estimation of distributed algorithm