基于遗传禁忌算法考虑转运约束的并行机批量调度问题研究_柳龙华.pdf

第 28 卷 第 1 期2023 年 2 月工业工程与管理Industrial Engineering and ManagementVol.28 No.1Feb.2023基于遗传禁忌算法考虑转运约束的并行机批量调度问题研究柳龙华1，陈晶晶2*，姜秀梅1，陈桥1，武斌功1，管在林2（1.中国电子科技集团公司第三十八研究所，安徽 合肥 230088；2.华中科技大学 机械科学与工程学院，湖北 武汉 430074）摘要:在多品种混流生产车间里，广泛存在着各种批量的任务在多台并行机上调度优化问题。这种并行机批量调度需要考虑批量大小设置、加工顺序优化、设备充分利用等多种要素，是一类典型NP-hard问题，且当任务加工完后还需要考虑转运过程时，问题将变得更加复杂。为了减少并行机生产过程中任务拖期和在制品积压，寻求更好的生产调度方案，针对典型并行机生产和转运场景，以最小化加权完工时间及拖期工件的惩罚费用、作业切换成本、库存成本之和为优化目标，设计了基于启发式规则的仿真程序与遗传禁忌算法相结合的优化算法，研究单工序不相关并行机调度环境下车间批量调度的最优调度方案，再通过案例验证了本文优化算法的有效性。结果表明，优化算法得出的并行机批量调度方案使得作业切换次数和拖期订单大大减少，减少在制品库存的同时提高了转运资源的利用率。关键词:并行机调度；转运约束；批量调度；仿真程序；遗传禁忌算法中图分类号:F 406 文献标识码:AResearch on Parallel Machine Batch Scheduling with Transport Constraints Based on Improved Genetic Tabu AlgorithmLIU Longhua1，CHEN Jingjing2*，JIANG Xiumei1，CHEN Qiao1，WU Bingong1，GUAN Zailin2（1.The No.38 Institute of China Electronic Technology Corporation，Hefei，Anhui 230088，China；2.School of Mechanical Science&Technology，Huazhong University of Science and Technology，Wuhan，Hubei 430074，China）Abstract:The scheduling optimization problem with various batch tasks on multiple parallel machines widely exists in multi-variety mixed-flow production shop.This kind of problem needs to consider batch size，processing sequence optimization，full utilization of the equipment and other elements.It is a typical NP hard problem.When the task after processing also needs to be considered during the transfer process，the problem will get more complicated.In order to reduce task delay and work-in-process backlog in parallel machine production，to get a better production scheduling result，an optimization algorithm based on heuristic rules and genetic tabu algorithm was designed in order to 文章编号：1007-5429（2023）01-0059-08DOI：10.19495/ki.1007-5429.2023.01.008收稿日期：2021-05-08基金项目：国防基础科研计划（JCKY2018210B003）作者简介：柳龙华（1981），山东莒县人，高级工程师，博士，主要研究领域为雷达电子装备先进制造和智能制造技术研究。E-mail：。*通信作者：陈晶晶，硕士研究生，主要研究方向为生产调度与系统仿真。E-mail：。-59第 28 卷 柳龙华，等：基于遗传禁忌算法考虑转运约束的并行机批量调度问题研究minimize the sum of weighted completion time，penalty cost，job switching cost and inventory cost.This paper studied the optimal scheduling method of batch shop scheduling under single process uncorrelated parallel machine scheduling environment，and verified the effectiveness of the optimization algorithm through a case study.The results show that the parallel machine batch scheduling method obtained by the optimization algorithm，can greatly reduce the number of job switching and delayed orders，reduce the work-in-process inventory and improve the utilization rate of transfer resources.Key words:parallel machine scheduling;transport constraint;batch scheduling;simulation program;genetic tabu algorithm1 介绍 随着市场竞争的日趋激烈，生产企业需要以更加灵活的方式和更加丰富的产品种类快速响应市场需求。并行机批量调度一直以来都是NP-hard问题1，其除了需要考虑加工设备和顺序等变量，还需要优化分批方案和子批大小等变量，解的搜索空间还会随着调度规模变大而呈指数增长，因此这类问题需要有效的优化算法来解决2-3。许多学者在并行 机 批 量 调 度 方 面 已 经 进 行 了 研 究，例 如ROCHOLL4等以最小化总加权延迟和电力成本为优化目标，设计了3种基于分组遗传算法的启发式算法来解决并行批处理机器上作业调度的模型问题。文献 5-7 为了解决平行机批量调度问题，以完工时间为优化目标，采用了模拟退火算法和遗传算法进行求解。SCHIMIDT8等研究了考虑并行机器生产环境下的两阶段批量排序问题，提出了两种数学模型和多种基于问题分解的启发式策略来解决实际数据适应的实例问题。XUAN9等以优化生产周期为目标，采用两段矩阵编码方法解决批次划分和分批排序问题，提出基于模型约束的遗传算法来研究钢琴生产的批量调度问题。以上研究多采用优化算法来解决并行机批量调度问题，为了更好地解决实际生产问题，现阶段研究解决了具有转运资源约束的并行机批量调度问题。ZHANG10等研究了具有运输约束和加工时间有限的柔性作业车间调度问题，提出了一种混合遗传算法、禁忌局部搜索和改进的移动瓶颈算法。WANG11等研究了具有可变的子批大小和运输活动容量限制等约束的并行机批量流车间调度问题，为了最小化最大完工时间/总流程时间，提出了一种三阶段方法。ABDERRAHIM12等以最大限度减少作业的最大完成时间为目标，提出了考虑特定产品制造任务的加工资源和零件运输资源约束的可变邻域搜索算法。由于本文研究的是具有转运资源约束的并行机批量调度问题，而且还考虑了实际生产环境中的其他约束，具有较强的应用背景，所以该研究具有显著的现实意义与理论价值。本文将面向离散制造业车间，在产品需求确定，设备数量已知的情况下，以最小化加权完工时间及制造成本为目标，设计了考虑台车数量约束的改进遗传禁忌算法，研究单工序不相关并行机调度环境下车间批量调度的最优调度方案。2 问题描述与数学模型 本文研究了考虑转运资源台车数量约束的最优作业切换下的不相关并行机批量调度问题。其中，各品种工件在不同机器上的节拍时间已知，待加工池中有多个批次的工件订单，每个工件加工完成后需占用一台对应台车用于临时存储，订单交期到达时释放相应台车，不同种类的工件对应不同型号台车，每种台车可装工件的数量已知，各类型台车数量已知。问题的优化目标是最小化加权完工时间及拖期工件的惩罚费用、作业切换成本和库存成本之和。需要确定各加工子批的数量、大小以及各加工子批在各机器上的分配，同时每个生产批次需要满足最小生产批量的要求。该问题的数学规划模型可以描述为：有M台不相关并行机加工G种类型的工件；有O个订单，不同的订单中工件的型号、批量大小、交货期不完全相同。调度优化决策包括根据-60第 1期工 业 工 程 与 管 理交期和台车数量约束对分配到不同并行机上加工子批的数量、批量大小以及加工子批的生产排序进行优化，使生产线的作业切换次数最少。2.1模型假设（1）所有工件在t=0时刻到达，不考虑机器等待的时间；（2）每台机器每次最多加工一个工件，且工件不可中断；（3）所有机器在t=0时刻都可以使用；（4）忽略台车有关的运输、装卸时间；（5）各个工件在不同设备上的加工时间是给定值。2.2模型建立问题参数如下。i：台车的类型编号，i1，2，I；m：机器编号，m1，2，M；t：时间编号，t1，2，T；j：工件编号；g：工件类型编号，g1，2，G；o：订单编号，o1，2，O；k：订单在机器上加工位置编号，k1，2，K；bo：订单o拆分得到的加工子批，bo1，2，Bo；go：订单o对应工件的类型；to：订单o的交货期；Jo：订单o中工件的订货批量；jbo：订单o所拆分得到的加工子批b中工件的编号，jbo1，2，Jbo；TFm：机器m上的不可加工时间段，TFmt|tm1ttm2，tm，2f-1ttm，2f；Sjbo：工件jbo的开始加工时间，j1，2，Jbo，b1，2，Bo，o1，2，O；Cjbo：编号为b的批次中工件加工结束的时间，j1，2，Jbo，b1，2，Bo，o1，2，O；Gm：机器m可加工的工件类型；Pgm：g类型工件在机器m上加工所需的时间，g1，2，G，m1，2，M，若gGm，则Pgm=0；Rtg：t时 刻g类 型 工 件 的 完 成 品 库 存 量，t1，2，T，g1，2，G；Atg：t时刻g类型工件的新增完成品数量，t1，2，T，g1，2，G；Vi：类型为i的台车可储存工件的个数；Gi：类型为i的台车可以存储工件类型的集合；Ni：类型为i的台车总量；hj：单位工件j单位时间内的在制品库存成本。决策变量如下。Bo：订单o被拆分为加工子批的个数，o 1，2，O；Jbo：订单o所拆分得到的加工子批b中所包含工件个数，b=1BoJbo=Jo；Xbokm：0-1变量，若订单o拆分得到的加工子批bo在机器m的位置k上加工则为1，否则为0；eps：加工子批的最小批量。目标函数的参数如下。W：目标函数值，最大完工时间与制造成本的加权值；w1：完工时间在目标函数中所占比重；w2：制造成本在目标函数中所占比重；Tar：拖期工件数，所有拖期订单包含的工件数量之和；Cha：换模次数；：拖期工件的惩罚费用；：换模一次所需要的费用；：库存成本；Cmax：完工时间。目标函数：minW=w1Cmax+w2（Tar+Cha+）（1）拖期工件、换模次数