一类具有特殊阻塞约束的两阶段流水车间成组调度模型与算法  

Model and algorithm for two-stage flow shop group scheduling problem with special blocking constraint

作　　者：袁帅鹏 李铁克[1,2] 王柏琳[1,2] 余娜娜 YUAN Shuai-peng;LI Tie-ke;WANG Bai-lin;YU Na-na(Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China;Engineering Research Center of MES Technology for Iron&Steel Production,Beijing 100083,China)

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

出　　处：《控制与决策》2020年第7期1773-1779,共7页Control and Decision

基　　金：国家自然科学基金项目(71701016,71231001);北京市自然科学基金项目(9174038);教育部人文社会科学研究青年基金项目(17YJC630143);中央高校基本科研业务费专项基金项目(FRF-BD-18-009A)。

摘　　要：从钢铁企业的管加工生产中抽象出一类具有特殊阻塞约束的两阶段流水车间成组调度问题.与传统阻塞约束不同,工件是否发生阻塞并非取决于缓冲区容量,而是取决于工件自身的规格、尺寸等属性.针对此调度问题,以最小化最大完工时间(makespan)为目标建立混合整数线性规划模型,并通过三划分问题的多项式归结证明问题的强NP难特性,进而将问题划分为工件组排序和工件组内工件排序两个子问题,提出一种基于协同进化的分布估计算法.算法针对两个子问题各自特点进行独立编码,分别设计启发式规则构造初始种群,并提出带有工件区块结构特征的概率模型来指导种群进化.基于实际生产数据设计多种问题规模的实验,从而表明所提出模型和算法的有效性.A two-stage flow shop group scheduling problem with special blocking constraint is investigated based on the production reality of pipe-processing workshops in steel industry.In contrast to traditionally used blocking constraints,we use the attributes of the jobs,not the quantity of jobs in the current buffer area,to determine the need for a blocking feature.Firstly,the mixed integer linear programming model that minimizes the makespan is established,and it is proved that the problem is strongly NP-hard by reduction of the 3-partition problem.The co-evolutionary estimation of distributed algorithm(CEDA)is proposed according to the problem characteristics,in which the group sequence and the job sequence within each group are encoded independently.Heuristic rules based on the features of the sub-problems are provided to construct the initial population.Moreover,a block-based probabilistic model is designed to guide the population evolution.A variety of scale experiments based on the actual production data are carried out,and the result shows the effectiveness of proposed model and algorithm.

关 键 词：流水车间 成组调度 阻塞约束 协同进化 分布估计算法 

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