工件可拒绝的有限等待置换流水车间调度算法  

Scheduling algorithm for permutation flowshop with limited waiting times and rejection

作　　者：王柏琳[1,2] 王海凤[1,2] 李铁克[1,2] WANG Bai-lin;WANG Hai-feng;LI Tie-ke(Donlinks School of Economics and Management,University of Science and Technology Beijing,Beying 100083,China;Engineering Research Center of MES Technology for Iron&Steel Production,Ministry of Education.Beijing 100083,China)

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

出　　处：《控制与决策》2019年第3期459-469,共11页Control and Decision

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

摘　　要：有限等待限定了工件在相邻机器间的等待时间上下限,普遍存在于中间产品性质不稳定且存在运输作业的车间环境中.工件可拒绝的有限等待置换流水车间调度是对工件拒绝和工件调度的联合决策,要求确定拒绝工件集合并给出被接受工件的调度方案.针对这一联合决策问题,以最小化总拒绝成本与总拖期成本之和为目标,并为最大完工时间(Makespan)设置上限约束,结合问题特征提出一种协同进化遗传算法.该算法将染色体编码分解为工件拒绝和工件序列两个子集,基于调度规则生成初始种群,引入协同进化策略依次进化子集种群,并提出基于记忆的动态概率参数设计方法以确定遗传算子的执行概率,设计解码规则以保证解的可行性并优化总成本.最后,通过数据实验验证了所提出算法及相关策略的可行性和有效性,并分析了问题参数对算法性能的影响.Limited waiting time constraint restricts the maximal and minimal waiting times of a job between consecutive machines. This constraint widely exist in the manufacturing environment with transportation requirement and high production continuity due to the unstable physical or chemical nature of intermediate product. The permutation flowshop scheduling problem with rejection is a joint decision of job rejection and production scheduling, which is to determine rejected jobs and the schedule with accepted jobs. This joint decision problem is considered with the objective to minimize the sum of total rejection cost and total tardiness cost, and an upper bound is set for the makespan in this problem. A co-evolutionary genetic algorithm is presented, in which an encoding scheme is proposed to divide a chromosome into two subsets, respectively corresponding to job rejection and job sequencing. The initial population is produced by dispatching rules, and the co-evolutionary strategy is introduced into this algorithm to coevolve the two subset population. Moreover,a memory-based dynamic probability generation method is presented to determine the probabilities to run the genetic operators, and some decoding rules are set to ensure the feasibility of a solution and optimize its total cost. Computational experiments are carried out to verify the effectiveness of this algorithm, and the impact of problem parameters on the performance of this algorithm are also studied in the experiments.

关 键 词：生产调度 工件拒绝 置换流水车间 有限等待 遗传算法 协同进化 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]