一类具有成组可重入特征单机调度的改进分布估计算法  

An Improved Estimation of Distributed Algorithm for A Single Machine Scheduling Problem with Re-entrant and Group Features

作　　者：袁帅鹏 李铁克[1,2] 王柏琳[1,2] 张文新[1,2] 张卓伦 余娜娜 YUAN Shuaipeng;LI Tieke;WANG Bailin;ZHANG Wenxin;ZHANG Zhuolun;YU Nana(School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China;Engineering Research Center of MES Technology for Iron&Steel Production,Ministry of Education,Beijing 100083,China)

机构地区：[1]北京科技大学经济管理学院,北京100083 [2]钢铁生产制造执行系统技术教育部工程研究中心,北京100083

出　　处：《运筹与管理》2023年第8期78-84,共7页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71701016);北京市自然科学基金资助项目(9174038);中央高校基本科研业务费专项资金项目(FRF-BD-20-16A)。

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

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

分 类 号：TH165[机械工程—机械制造及自动化]