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

摘要： 从钢铁企业宽厚板热轧生产过程中提炼出一类具有成组可重入特征的单机调度问题。在该问题中,工件需分阶段重复进入同一机器加工,且阶段间存在一定的等待时间,为提升生产效率,允许相邻工件进行成组加工。针对此类具有实际工业应用背景的调度问题,以最大完工时间为目标,首先建立了混合整数线性规划模型,然后证明了问题的强NP难特性,并给出了最优解存在的性质特征,进而开发了一种改进的分布估计算法,为评估算法性能,基于理论分析提出了问题最优解的两个下界。通过与其他三种主流元启发式算法的比较分析,验证了所提算法的有效性。

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