基于混合迭代贪婪算法的分布式车间调度研究

计算机测量与控制．２０２０．２８（１１）　犆狅犿狆狌狋犲狉犕犲犪狊狌狉犲犿犲狀狋牔犆狅狀狋狉狅犾　·２１６　·收稿日期：２０２００４１６；　修回日期：２０２００５１２。

基金项目：国家自然科学基金项目（６１４７３２１６）；陕西省教育厅科学研究计划项目（１７ＪＫ０４５９）；西安建筑科技大学基础研究项目（ＺＲ１８０４９）；陕西省自然科学面上项目（２０２０ＪＭ－４８９）。

作者简介：陈 翰（１９９４），男，重庆人，硕士研究生，主要从事智能制造、优化算法、人工智能方向的研究。

通讯作者：熊福力（１９７４），男，黑龙江肇东人，硕士生导师，副教授，主要从事人工智能与系统优化、生产计划与调度优化、智能建筑方向的研究。

文章编号：１６７１４５９８（２０２０）１１０２１６０６ ＤＯＩ：１０．１６５２６／ｊ．ｃｎｋｉ．１１－４７６２／ｔｐ．２０２０．１１．０４４ 中图分类号：ＴＵ７５６文献标识码：Ａ基于改进迭代贪婪算法的预制构件调度研究陈 翰，熊福力，曹劲松，李　志（西安建筑科技大学信息与控制工程学院，西安　７１００５５）摘要：迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法，但由于传统迭代贪婪算法搜索范围过大，搜索效率有限，为了进一步提升传统迭代贪婪算法的搜索能力，考虑到阈值接受算法具有能缩小搜索范围的特点，提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题；该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略，并结合阈值接受算法的自适应接受准则用以跳出局部最优；经大量仿真实验结果显示，与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比，改进的迭代贪婪算法具有更好的求解质量和鲁棒性。

关键词：迭代贪婪算法；阈值接受算法；流水车间；订单接受与调度犚犲狊犲犪狉犮犺狅狀犛犮犺犲犱狌犾犻狀犵狅犳犘狉犲犳犪犫狉犻犮犪狋犲犱犆狅犿狆狅狀犲狀狋狊犅犪狊犲犱狅狀犕狅犱犻犳犻犲犱犐狋犲狉犪狋犻狏犲犌狉犲犲犱狔犃犾犵狅狉犻狋犺犿ＣｈｅｎＨｏｎｇｈａｎ，ＸｉｏｎｇＦｕｌｉ，ＣａｏＪｉｎｓｏｎｇ，ＬｉＺｈｉ（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｎｔｒｏｌＥｎｇｉｎｅｅｒｉｎｇ，Ｘｉ ａｎＵｎｉｖｅｒｓｉｔｙｏｆＡｒｃｈｉｔｅｃｔｕｒｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｉ ａｎ　７１００５５，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：Ｉｔｅｒａｔｉｖｅｇｒｅｅｄｙ（ＩＧ）ａｌｇｏｒｉｔｈｍｉｓａｍｅｔａ－ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｗｉｔｈｓｔｒｏｎｇｌｏｃａｌｓｅａｒｃｈａｂｉｌｉｔｙ，ｂｕｔｄｕｅｔｏｔｈｅｅｘｃｅｓｓｉｖｅｓｅａｒｃｈｒａｎｇｅｏｆｔｒａｄｉｔｉｏｎａｌｉｔｅｒａｔｉｖｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍａｎｄｌｉｍｉｔｅｄｓｅａｒｃｈｅｆｆｉｃｉｅｎｃｙ，ｉｎｏｒｄｅｒｔｏｆｕｒｔｈｅｒｉｍｐｒｏｖｅｔｈｅｓｅａｒｃｈａｂｉｌｉｔｙｏｆｔｒａ ｄｉｔｉｏｎａｌｉｔｅｒａｔｉｖｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ，ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｔｈｒｅｓｈｏｌｄａｃｃｅｐｔａｎｃｅａｌｇｏｒｉｔｈｍｈａｓｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｎａｒｒｏｗｉｎｇｔｈｅｓｅａｒｃｈｒａｎｇｅ，ａｎｉｍｐｒｏｖｅｄｉｔｅｒａｔｉｖｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｏｒｄｅｒａｃｃｅｐｔａｎｃｅａｎｄｓｃｈｅｄｕｌｉｎｇｆｏｒｐｒｅｆａｂｒｉｃａｔｅｄｐｒｏｄｕｃｔｉｏｎｉｎｆｌｏｗｓｈｏｐ．Ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｓｔｏａｄｄａｒｅｃｏｎｓｔｒｕｃｔｉｏｎｓｔｒａｔｅｇｙｂａｓｅｄｏｎｃｏｎｓｔｒｕｃｔｉｎｇｈｅｕｒｉｓｔｉｃｒｕｌｅｓａｆｔｅｒｄｅｓｔｒｏ ｙｉｎｇｔｈｅｏｒｉｇｉｎａｌｓｃｈｅｄｕｌｉｎｇｓｅｑｕｅｎｃｅ，ａｎｄｃｏｍｂｉｎｅｄｗｉｔｈｔｈｅａｄａｐｔｉｖｅａｃｃｅｐｔａｎｃｅｃｒｉｔｅｒｉｏｎｏｆｔｈｅｔｈｒｅｓｈｏｌｄａｃｃｅｐｔａｎｃｅａｌｇｏｒｉｔｈｍｔｏｊｕｍｐｏｕｔｏｆｔｈｅｌｏｃａｌｏｐｔｉｍｕｍ．Ａｌａｒｇｅｎｕｍｂｅｒｏｆｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄｉｔｅｒａｔｉｖｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｈａｓｂｅｔ ｔｅｒｓｏｌｕｔｉｏｎｑｕａｌｉｔｙａｎｄｒｏｂｕｓｔｎｅｓｓｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｔｒａｄｉｔｉｏｎａｌｉｔｅｒａｔｉｖｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ，ｔａｂｕｓｅａｒｃｈ（ＴＳ）ａｌｇｏｒｉｔｈｍａｎｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ（ＧＡ）．犓犲狔狑狅狉犱狊：ｉｔｅｒａｔｉｖｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ；ｔｈｒｅｓｈｏｌｄａｃｃｅｐｔａｎｃｅａｌｇｏｒｉｔｈｍ；ｆｌｏｗｓｈｏｐ；ｏｒｄｅｒａｃｃｅｐｔａｎｃｅａｎｄｓｃｈｅｄｕｌｉｎｇ０　引言在混凝土预制构件生产的系统中，利润最大化是企业的首要目标。

算法2023-11-09contents •引言•多车间综合调度问题概述•混合算法设计•算法实现与实验验证•结论与展望目录01引言制造业的快速发展使得车间调度问题变得越来越重要，车间调度问题的解决对于提高生产效率、降低生产成本、提高产品质量等方面都具有重要的意义。

随着信息技术和人工智能的不断发展，混合算法作为一种先进的求解策略，被广泛应用于解决各种复杂问题，包括多车间综合调度问题。

研究背景与意义研究现状与挑战目前，对于多车间综合调度问题的研究已经取得了一定的成果，但是仍然存在许多挑战。

传统的求解方法通常基于规则或经验，难以处理复杂的多车间调度问题，且容易受到环境变化和不确定因素的影响。

近年来，混合算法在求解复杂问题方面表现出了优异的性能，但是如何将其有效应用于多车间综合调度问题仍存在一定的难度。

研究内容与方法本研究旨在利用混合算法的思想，设计一种适用于多车间综合调度问题的求解方法。

其次，采用遗传算法、模拟退火算法和蚁群算法等混合算法的思想，设计一种求解多车间综合调度问题的混合算法。

首先，对多车间综合调度问题进行建模，包括任务分配、加工顺序、加工时间等方面的约束。

最后，通过实验验证所设计的混合算法的有效性和优越性。

02多车间综合调度问题概述多车间综合调度问题（Multi-shop Scheduling Problem，MSSP）是指在一个制造系统中，多个工作车间需要进行任务分配、时间和资源规划的问题。

特点包括：考虑多个车间之间的交互和约束，任务具有不同的优先级和交货期，需要合理安排任务执行顺序和时间，以最小化总生产成本和交货时间。

问题定义与特点约束条件包括：每个任务必须在指定的时间内完成，每个车间在同一时间内只能执行一个任务，任务的执行顺序不能改变等。

优化目标是最小化总生产成本和交货时间，或者在满足约束条件下最小化其他指标，如总加班时间、总设备空闲时间等。

问题约束与优化目标问题求解方法与评估标准求解方法包括启发式算法、元启发式算法、精确算法等。

混合遗传算法在车间调度中的应用的开题报告1.研究背景车间调度是制造企业不可或缺的一个环节。

在制造企业中，车间调度涉及到车间机器设备的配置和修理，以及工人和生产线的协调和管理等复杂问题。

车间调度的目标通常是通过合理的调度方案来实现最优化的生产效益，从而提高生产效率，降低成本，增加企业盈利。

传统的车间调度方法往往是基于人工经验和试错的方式来制定调度规划，这种方法的缺点是耗时、耗力，且往往不能达到最优化的效果。

因此，在车间调度中引入智能优化算法来求解最优调度方案成为一种趋势，其中混合遗传算法近年来成为研究热点。

2.研究目的本文旨在研究混合遗传算法在车间调度中的应用，探究其优势和不足，并尝试提出一种改进的混合遗传算法，以提高车间调度方案的优化效果和实际可行性。

3.研究内容3.1 混合遗传算法的基本原理和步骤本文首先介绍混合遗传算法的基本原理和步骤，包括遗传算法和局部优化算法的结合、个体表达、适应度函数、选择、交叉、变异等。

3.2 车间调度问题的描述和建模本文进一步探讨车间调度问题的描述和建模方法，包括车间任务、车间机器设备、优先级、作业时间等的定义和表示。

3.3 混合遗传算法在车间调度中的应用本文探究混合遗传算法在车间调度中的应用，包括求解车间调度问题的具体步骤和方法，以及基于混合遗传算法的车间调度方案的评估和优化。

3.4 算法改进本文基于对混合遗传算法在车间调度中的应用实践的总结，尝试提出一种改进的混合遗传算法。

改进的主要方向包括增加不同的适应度函数、调整遗传算法的参数和优化交叉和变异的方式等。

4.研究意义本文研究混合遗传算法在车间调度中的应用，可以帮助制造企业更加高效地进行生产调度和任务分配，提高产品的质量和企业的盈利能力，同时也可以为智能优化算法的研究和应用提供一定的参考和借鉴价值。

5.研究方案本文的研究方案包括以下几个步骤：5.1 文献综述对混合遗传算法、车间调度问题及其求解算法进行文献综述，包括分别从理论角度和实践应用角度进行分析，总结已有研究的成果和不足。

基于混合遗传算法的车间生产计划调度崔雪丽【期刊名称】《计算机工程与设计》【年(卷),期】2011(32)7【摘要】针对车间环境的动态随机性、多工序问题,研究了调度问题和算法的特征,提出了一种基于混合遗传算法的车间调度方案.在传统遗传算法的基础上,采用交叉算子、变异算子与启发式算子结合,实现了混合遗传算法,避免了传统遗传算法解的不可行性.再把紧急工序作为一个时域段,结合可变时域滚动机制,实现了可插入紧急工序的调度算法,使一道工序不需重新调度也可排入作业计划,避免了不可插入性,节省了时间,提高了效率.结合实例进行仿真分析,结果表明了调度的可行性、正确性、满意度.%The job shop schedule scheme based on the hybrid genetic algorithm is developed for the random of work shop environment and problem of procedures by studying job shop schedule problem and algorithm character. First, the hybrid genetic algorithm is implemented using heuristic crossover and mutation operators based genetic algorithm, avoiding tradition genetic algorithm inaccuracy. Second, taking emergency procedures as a rolling window combined the rolling window being time-based, the schedule algorithm of inserted emergency procedures is implemented, in which emergency procedures may be arranged work shop plan while not be scheduled over again, reducing time and improving efficiency. It ensures the correctness of schedule and the degree of being pleased with schedule.【总页数】6页(P2467-2471,2475)【作者】崔雪丽【作者单位】西北工业大学软件与微电子学院,陕西西安710072【正文语种】中文【中图分类】TP319【相关文献】1.中小型企业车间生产计划调度问题及优化 [J], 郝冠男2.基于Web的复合材料车间生产计划调度信息系统构建 [J], 李锡华;范玉青;梅中义3.基于混合遗传算法的车间生产调度问题研究 [J], 黄巍;张美凤4.一种基于混合遗传算法的车间生产调度的研究 [J], 刘红军;赵帅5.基于混合遗传算法的车间作业计划调度方法 [J], 崔广才;陶丽华;杨敬松因版权原因，仅展示原文概要，查看原文内容请购买。

基于混合遗传算法的MES车间调度系统研究的开题报告一、选题背景及意义近年来，随着信息技术的飞速发展和制造业的不断发展，制造企业面临的竞争压力越来越大，而MES(MANUFACTURING EXECUTION SYSTEMS)车间调度系统的开发和应用可以帮助制造企业提高生产效率和降低生产成本，更好的满足市场需求，从而增强企业核心竞争力。

MES车间调度系统是指利用计算机等信息技术手段，对企业的生产过程进行实时管理和监控的系统。

该系统通过对生产过程进行规划、指挥和监督等操作，实现对生产过程的优化、调度和控制。

同时，MES系统还可以对生产过程中的各个环节的数据进行采集、分析和处理，生成相应的报表和图表，为管理层提供决策支持。

然而，MES系统在设计和实现调度算法时面临的问题和挑战也是很大的，比如在进行任务调度时，需要考虑许多因素，例如生产工艺、原材料、加工设备、人工、能源等，需要进行综合考虑和协调；另外，MES 系统的优化目标也不只是提高生产效率，还需考虑成本、质量、环保等因素。

因此，对于MES系统的调度算法的研究对于提高制造企业的生产效率和核心竞争力具有重要的意义。

二、研究内容和方法本文将研究基于混合遗传算法的MES车间调度系统，主要包括以下研究内容：1. MES系统的功能和调度算法原理研究：介绍MES系统的主要功能和调度算法的原理，分析MES系统中任务调度的基本特点和要求。

2. 混合遗传算法的原理和应用：介绍混合遗传算法的基本原理和应用，分析混合遗传算法在任务调度问题中的适用性和优势。

3. 基于混合遗传算法的MES车间调度模型设计：根据MES系统的调度要求和混合遗传算法的原理，设计适用于MES系统的混合遗传算法模型，包括编码方案、评价函数和进化算子等。

4. 基于模拟实验的MES车间调度实现和优化：采用MATLAB等工具，以某工厂为例，实现MES车间调度模型，并进行模拟实验和结果分析。

通过比较混合遗传算法和其他调度算法的效果和优劣，验证混合遗传算法的优越性。

分布式车间调度优化算法研究综述【分布式车间调度优化算法研究综述】各位朋友，大家好！今天咱们来聊聊那个让人头疼的问题——怎么让生产线上的小车们高效协同工作。

别急，听我给你娓娓道来。

首先得提提“多任务并行”这个点子。

想象一下，你面前有一堆活儿，每个活儿都等着被处理。

要是咱们能同时搞定几个活儿，那效率岂不是嗖嗖的？这就是分布式车间调度的精髓所在，它就像是个超级大脑，把分散的任务集中起来一起干。

再来说说“智能匹配”这个招儿。

就像找对象一样，得看对眼不。

在生产车间里，机器和原料也得找个合适的搭档才能发挥最大效能。

智能匹配算法就像个媒人，帮它们找到最合适的组合，让生产流程顺畅无阻。

别忘了“动态调整”这招儿。

生产线上的情况千变万化，就像天气一样。

有时候风平浪静，有时候狂风暴雨。

这时候，调度系统就得像个灵活的舵手，根据实时情况调整生产计划，确保小船稳稳当当。

再来说说“资源优化”这个事儿。

就像超市里的货架，东西得按类别放，这样顾客一进店就能轻松找到自己想要的商品。

在车间里，资源的合理分配能让生产更有效率，减少浪费。

咱们得说说“用户体验”。

虽然咱们讲的是生产，但用户体验也不能落下。

一个友好的用户界面，能让工人轻松上手，不用被复杂的操作搞晕头转向。

总的来说，分布式车间调度优化是一个复杂但有趣的话题。

它涉及到了人工智能、机器学习、运筹学等多个领域。

通过不断地研究和实践，我们相信未来的工厂会变得更加智能、高效和人性化。

朋友们，你们觉得这些方法怎么样？是不是感觉既实用又有趣？下次再聊，咱们可以探讨一下最新的研究成果或者行业趋势哦！。

第３４卷第１３期中国机械工程V o l ．３４㊀N o ．１３２０２３年７月C H I N A M E C HA N I C A LE N G I N E E R I N Gp p．１５７６Ｇ１５８８基于多目标混合进化算法的作业车间混排可变分批节能调度方法谢法吾㊀李玲玲㊀李㊀丽㊀黄洋鹏西南大学工程技术学院,重庆,４００７１５摘要:针对作业车间分批调度问题,集成可变子批划分和子批混排策略,考虑批量划分约束㊁子批混排加工约束等,建立了最小化能耗和完工时间的混排可变分批调度优化模型,并提出了一种改进多目标混合进化算法.为了协调算法的全局搜索与局部搜索性能,将J a y a 算法种群更新机制引入基于分解的多目标进化算法中,同时结合混排可变分批调度问题特征,设计了一种基于子批拆分/合并与关键链相结合的局部搜索策略.基于不同规模算例,对比分析了所提出的算法与其他经典算法的求解性能.实验结果表明,所提出的算法在P a r e t o 解集收敛性和分布性方面具有明显优势,同时所提出的混排可变分批策略可有效降低能耗㊁缩短完工时间.关键词:作业车间;分批调度;可变分批;子批混排;进化算法中图分类号:T H １６２D O I :１０．３９６９/j．i s s n ．１００４ １３２X．２０２３．１３．００７开放科学(资源服务)标识码(O S I D ):E n e r g y Ｇe f f i c i e n t J o bS h o p S c h e d u l i n g w i t hV a r i a b l eL o t S p l i t t i n g a n dS u b l o t s I n t e r m i n g l i n g B a s e do n M u l t i Ｇo b j e c t i v eH y b r i dE v o l u t i o n a r y A l go r i t h m X I EF a w u ㊀L IL i n g l i n g ㊀L IL i ㊀HU A N G Y a n g p e n gC o l l e g e o fE n g i n e e r i n g a n dT e c h n o l o g y ,S o u t h w e s tU n i v e r s i t y ,C h o n g q i n g,４００７１５A b s t r a c t :F o r s o l v i n g t h e l o t s t r e a m i n g j o b s h o p s c h e d u l i n g ,a s t r a t e g y w a s p r e s e n t e d i n t e g r a t i n gv a r i a b l es u b l o t ss p l i t t i n g a n ds u b l o t s i n t e r m i n g l i n g ,a n da m u l t i Ｇo b j e c t i v eo pt i m i z a t i o n m o d e l o f l o t s t r e a m i n g s c h e d u l i n g w a se s t a b l i s h e dt o m i n i m i z et h ee n e r g y c o n s u m p t i o na n d m a k e s p a n ．A ni m Ｇp r o v e dm u l t i Ｇo b j e c t i v e h y b r i d e v o l u t i o n a r y a l g o r i t h m w a s p r e s e n t e d ．I n o r d e r t o b a l a n c e t h e g l o b a l a n d l o c a l s e a r c h i n g a b i l i t y o f t h e a l g o r i t h m ,t h e p o p u l a t i o nu p d a t i n g m e c h a n i s mo f t h e J a y a a l g o r i t h m w a s i n c o r p o r a t e d i n t ot h ed e c o m p o s i t i o n b a s e d m u l t i Ｇo b j e c t i v ee v o l u t i o n a r y a l g o r i t h m．C o n s i d e r i n g th e s c h e d u l i n g c h a r a c t e r i s t i c s o f v a r i a b l e l o t s p l i t t i n g a n d s u b l o t s i n t e r m i n g l i n g ,a l o c a l s e a r c h i n g s t r a t e g yw a s d e s i g n e d i n t e g r a t i n g l o t s p l i t t i n g /m e r g i n g w i t h c r i t i c a l p a t h ．T h e p e r f o r m a n c e o f t h e p r o po s e d a l Ｇg o r i t h ma n d t h e s t a t e Ｇo f Ｇt h e Ｇa r t a l g o r i t h m sw e r e c o m p a r e du n d e r a s e t o f i n s t a n c e s o f d i f f e r e n t s c a l e s ．E x p e r i m e n t a l r e s u l t s s h o wt h a t t h e p r o p o s e d a l g o r i t h mh a s g o o d p e r f o r m a n c e o n t h e c o n v e r ge n c e a n d d i s t r i b u t i o no fP a r e t os o l u t i o ns e t s ．M o r e o v e r ,t h e p r o p o s e dv a r i a b l e l o t s p l i t t i n g an ds u b l o t s i n t e r Ｇm i n g l i n g s t r a t e g y m a y e f f e c t i v e l y r e d u c e t h e e n e r g y c o n s u m p t i o na n dm a k e s pa n ．K e y wo r d s :j o b s h o p ;l o t s t r e a m i n g s c h e d u l i n g ;v a r i a b l e l o t s p l i t t i n g ;s u b l o t s i n t e r m i n g l i n g ;e v o Ｇl u t i o n a r y a l go r i t h m 收稿日期:２０２２１０１２基金项目:国家自然科学基金(５１９０５４４９,５１８７５４８０);重庆市自然科学基金(c s t c ２０２０j c y j Ｇm s x m X ０１２７);中央高校基本科研业务费专项资金(S WU ＧK T ２２０２３)０㊀引言在全球能源成本飙升和环境日益恶化的形势下,绿色节能的生产方式已成为制造领域的关注热点.车间调度作为制造系统生产控制的重要组成部分,是影响生产效率㊁成本的关键环节,同时调度方案将对车间能源消耗产生显著影响.在开展生产调度优化时,兼顾能源消耗㊁环境排放等绿色指标以及完工时间㊁延期交货时间等经济性指标,已成为绿色制造背景下的热点研究问题.国内外学者从不同角度出发,对流水车间[１Ｇ４]㊁作业车间[５Ｇ９]的节能调度问题开展了深入研究.其中,一类研究主要从机器分配和工序排序这两个子问题优化入手[１,３,５,７],以达到生产节能的目的.第二类研究则在机器分配和工序排序的基础上,引入了开/关机策略[２,８]㊁机器加工速度调节[９]以及分时电价机制[４],以最大化地降低能耗.现有的节能调度研究中,一部分研究聚焦于降低能耗[５],另一部分研究在考虑能耗目标的６７５１同时,还兼顾了完工时间[７,９]㊁延期交货时间[３,６]㊁成本[４]等经济性指标.节能调度问题的求解算法包括遗传算法[６,９]㊁进化算法[１,２,４]㊁人工蜂群算法[７]㊁J a y a算法[３]等.考虑到生产实际中存在的工件批量性以及批次可分特性,将分批策略与调度优化相结合,可进一步缩短完工时间㊁提高设备利用率和生产效率.目前,分批调度研究主要面向流水车间[１０Ｇ１３],只有少部分研究围绕作业车间分批调度问题[１４Ｇ１５]展开.同时,现有的分批调度研究较多着眼于完工时间[１３Ｇ１４]等经济性指标.近年来,节能分批调度优化问题开始受到国内外学者的关注并取得了初步成果[１０Ｇ１２,１５].现有的节能分批调度研究,根据车间类型分为流水车间[１０Ｇ１１,１５]和作业车间[１５];按批量划分策略分为一致子批[１０,１２,１５]和可变子批[１１]两种类型;根据子批排序类型不同,分为混排[１２,１５]和非混排[１０Ｇ１１]两种.例如,P A N等[１０]以分布式流水作业车间为对象,采用一致子批和非混排策略,并考虑能耗和完工时间目标,提出了一种基于J a y a算法的多目标分批调度优化方法. L I U等[１１]考虑能耗㊁完工时间和延期交货时间目标,基于可变子批和非混排策略,建立了混合流水作业车间分批调度模型,并采用多目标进化算法进行了求解.C H E N等[１２]以能耗和完工时间最小化为目标,考虑一致子批和混排策略,提出了基于改进遗传算法的混合流水车间分批调度方法.李聪波等[１５]以柔性作业车间为研究对象,考虑能耗和完工时间目标,提出了基于一致子批和混排策略的作业车间分批调度节能优化方法.现有的作业车间分批调度优化研究未考虑可变子批划分与子批混排策略的集成影响.对于多品种㊁中小批量的作业车间,由于各工件批量大小差异性以及工艺路线的离散性,将可变子批划分和子批混排策略相结合可进一步增加调度的灵活性,由此缩短机器空闲时间㊁提高机器利用率,并降低能耗.因此,基于可变子批划分与子批混排策略研究作业车间节能分批调度优化问题具有重要意义.然而,由于同时涉及可变子批划分与子批混排问题,要求各工件在各工序上的子批划分方案各不相同,且同一工件的各子批任务之间允许其他工件子批的混排加工,因此该调度问题相比于一致分批和非混排调度问题更加复杂.鉴于此,本文以多品种㊁中小批量的作业车间为研究对象,基于可变子批划分和子批混排策略,考虑能耗和完工时间目标,建立作业车间混排可变分批节能调度优化模型,并提出一种改进多目标混合进化算法求解该问题.为了协调算法的全局搜索与局部搜索能力,将J a y a算法种群更新机制引入基于分解的多目标进化算法中,同时结合混排可变分批调度问题特征,设计了一种基于子批拆分/合并与关键链相结合的局部搜索策略.最后基于不同规模算例,对比分析了所提出算法与其他经典算法的求解性能,以验证所提出算法的有效性和优势.１㊀调度问题描述及数学建模１．１㊀问题描述为更好地描述混排可变分批的作业车间节能调度问题,本文定义了表１所示的符号及其含义.问题描述如下:作业车间中共有K台机器M＝{M k|k＝１,２, ,K}和I个待加工工件J＝{J i| i＝１,２, ,I};每个工件J i由一批相同零件P i＝{P i,r|r＝１,２, ,N i}组成;每个工件的所有N i个零件均需经过n i道工序加工,且每个工件的每道工序所选择的机器是已知且确定的.每个工件J i在第j道工序上加工时,可被拆分为u i,j个子批,且每个子批s(∀s＝１,２, ,u i,j)所包含的零件数目为w i,j,s.采用可变子批划分策略时,同一个工件在各工序上被划分的子批数量u i,j及各子批的批量大小w i,j,s不尽相同,即同一个零件P i,r在不同工序上将被分配到不同的子批中.采用子批混排策略时,同一台机器上的同一个工件的各子批之间允许其他工件子批的插入加工.调度以总能耗和完工时间最小为目标,确定可变子批划分方案和子批混排调度方案.其中,可变子批划分方案是确定各工件在每道工序上划分的子批数量u i,j以及每个子批的批量大小w i,j,s(∀s＝１,２, ,u i,j);子批混排调度方案是确定所有子批在各机器上的混排加工顺序χi,j,s,k.该调度问题的假设条件描述如下:(１)所有工件在零时刻到达,所有机器在零时刻处于可用状态;(２)同一个子批中的所有零件必须连续加工,不可被其他子批的零件中断;(３)同一台机器加工相邻两个不同工件子批时将产生辅助操作(更换模具㊁夹具等)时间,且辅助操作必须在子批到达机器后才可开始;(４)当一个子批中的所有零件均结束当前工序的加工后才可被运输至下一道工序所对应的机器上;７７５１基于多目标混合进化算法的作业车间混排可变分批节能调度方法 谢法吾㊀李玲玲㊀李㊀丽等表１㊀相关参数及含义T a b．１㊀T h e d e f i n i t i o no f t h e r e l e v a n t p a r a m e t e r s参数符号参数含义参数符号参数含义i,iᶄ工件编号P s k机器M k的待机功率j,jᶄ工序编号e物流运输小车单位时间的电能消耗s,sᶄ子批编号πi,j工件J i的每个零件的第j道工序的加工时间r,rᶄ零件编号ε子批在不同个机器间的运输时间k机器编号θ在机器上更换模具㊁夹具等辅助操作的时间q加工顺序编号δi,j,s工件J i在第j道工序的第s个子批的辅助操作时间J＝{J i|i＝１,２, ,I}工件集合Φk,q机器M k开始加工第q个子批任务之前的空闲等待时间P i＝{P i,r|r＝１,２, ,N i}各工件的零件集合ξi,j,s,r０Ｇ１变量;ξi,j,s,r＝１表示工件J i的第r个零件在第j道工序中被分配到第s个子批中;反之,ξi,j,s,r＝０M＝{M k|k＝１,２, ,K}机器集合ηi,j,s,r工件J i的第r个零件在第j道工序的第s个子批中的加工顺序K机器总数s s t i,j,s工件J i在第j道工序的第s个子批的辅助操作开始时刻I工件总数c s t i,j,s工件J i在第j道工序的第s个子批的辅助操作结束时刻N i工件J i的批量大小a t i,j,s,r工件J i在第j道工序的第s个子批的第r个零件的到达时刻n i工件J i的工序总数A T i,j,s工件J i在第j道工序的第s个子批在机器上准备就绪时刻u i,j工件J i在第j道工序中划分的子批数量S T i,j,s工件J i在第j道工序的第s个子批的开始加工时刻w i,j,s工件J i在第j道工序的第s个子批的大小s t i,j,s,r工件J i在第j道工序的第s个子批的第r个零件的开始加工时刻Q k机器M k加工的子批总数C T i,j,s工件J i在第j道工序的第s个子批的结束始加工时刻R i,j工件J i的第j道工序所选择的机器编号c t i,j,s,r工件J i在第j道工序的第s个子批的第r个零件的结束加工时刻P m k机器M k的加工功率χi,j,s,k工件J i在第j道工序的第s个子批在机器M k上的加工顺序㊀㊀(５)每台机器在任一时刻只能加工一个子批的一个零件;一个零件同一时刻只能被一台机器加工.１．２㊀数学建模１．２．１㊀决策变量调度问题的决策变量包括:各工件在各道工序上划分的子批数u i,j,每个子批的批量大小w i,j,s,以及所有子批在各机器上的混排加工顺序χi,j,s,k.１．２．２㊀目标函数以总能耗E和完工时间C m a x最小为目标,建立目标函数如下:f＝m i n(E,C m a x)(１)㊀㊀(１)完工时间目标函数.以所有工件在最后一道工序上的最大完工时间为目标函数:C m a x＝m a x i(C T i,j,s),∀j＝n i,s＝u i,n i(２)㊀㊀(２)能耗目标函数.作业车间总能耗由机器能耗和物流运输能耗组成,其中,机器能耗包括辅助操作时段能耗㊁加工时段能耗㊁空闲时段能耗;物流运输能耗是各子批在各机器之间流转所产生的物流运输电能消耗.①辅助操作时段能耗E p r e.同一台机器在加工相邻两个不同工件子批时,因更换模具㊁夹具等辅助操作而产生电能消耗.辅助操作时段能耗E p r e与各子批的辅助操作时间δi,j,s有关:E p r e＝ I i＝１ n i j＝１ u i,j s＝１P s kδi,j,s㊀㊀∀R i,j＝k(３)δi,j,s＝θ㊀㊀i f㊀χi,j,s,k＝１㊀a n d㊀R i,j＝kθ㊀㊀e l s e i fχi,j,s,k＞１χiᶄ,jᶄ,sᶄ,k＝χi,j,s,k－１R i,j＝R iᶄ,jᶄ＝k{０㊀㊀e l s eìîíïïïïïï(４)㊀㊀②加工时段能耗E p r o.机器在加工各零件的过程中将产生加工时段能耗,加工时段能耗E p r o 与零件总数N i㊁加工时间πi,j以及机器加工时段功率P m k有关:E p r o＝ I i＝１ n i j＝１N i P m kπi,j㊀㊀∀R i,j＝k(５)由于零件总数N i㊁加工时间πi,j以及机器加工时段功率P m k均为定值,因而加工时段能耗E p r o也为一固定值,因此,E p r o不受可变子批划分方案和子批混排调度方案影响.③空闲时段能耗E i d l e.机器在加工相邻两个子批时将存在空闲等待时间,由此产生空闲时段能耗.空闲时段能耗E i d l e与机器空闲时长Φk,q成正比:E i d l e＝ K k＝１ Q q＝１P s kΦk,q(６)８７５１中国机械工程第３４卷第１３期２０２３年７月上半月Φk ,q ＝S T i ,j ,s ㊀㊀∀q ＝χi ,j ,s ,k ＝１a n d R i ,j ＝kS T i ,j ,s －C T i ᶄ,j ᶄ,s ᶄ㊀㊀∀q ＝χi ,j ,s ,k ＞１R i ,j ＝R i ᶄ,jᶄ＝k χi ᶄ,jᶄ,s ᶄ,k ＝q －１{ìîíïïïï(７)㊀㊀④物流运输能耗E t r a n s .各子批在各机器之间的运输,由物流运输小车完成,由此产生物流运输能耗.物流运输能耗E t r a n s 与子批数量u i ,j ㊁运输时间ε以及运输车功率e 有关:E t r a n s ＝Ii ＝１ n ij ＝１ui ,je ε(８)㊀㊀综上所述,辅助操作时段能耗E p r e ㊁空闲时段能耗E i d l e 以及物流运输能耗E t r a n s ,均与可变子批划分方案和子批混排调度方案直接相关,而机器加工能耗E p r o 不受工件分批方案和子批调度方案所影响,因此,本文的能耗目标函数中只考虑E p r e ㊁E i d l e ㊁E t r a n s :E ＝E p r e ＋E i d l e ＋E t r a n s(９)１．２．３㊀约束条件(１)可变子批划分约束.同一个工件在各工序上划分的子批数量以及各子批的批量大小不尽相同,同一个工件在每道工序上划分的子批批量的总和不能超过该工件的零件总数量:|u i ,j －u i ,j＋１|ȡ０㊀㊀㊀∀i ,j |w i ,j ,s －w i ,j＋１,s |ȡ０㊀㊀∀i ,j ,s }(１０) u i ,js ＝１wi ,j ,s ＝N i ㊀㊀∀i ,j(１１)㊀㊀(２)子批混排加工约束.同一台机器在加工同一个工件的不同子批之间,允许其他工件子批的插入加工:㊀χi ,j ,s ,k ＞０㊀㊀㊀∀i ,j ,s a n d R i ,j ＝kχi ,j ,s ,k ɤu i ,j ㊀㊀∀i ,j,s a n d R i ,j ＝k χi ,j ,s ,k ʂχi ,j ,s ,k ᶄ㊀∀i ,j ,s ʂs ᶄa n d R i ,j ＝k ᵑui ,j s ＝１[χi ,j ,s ,k －(χi ,j ,１,k －１)]－ᵑu i ,js ＝１s ȡ０㊀㊀㊀㊀㊀㊀㊀㊀㊀∀i ,j a n d R i ,j ＝küþýïïïïïïïï(１２)㊀㊀(３)各子批的辅助操作时间约束.当子批在机器上准备就绪且该机器处于空闲状态时才可开始辅助操作:㊀㊀s s t i ,j ,s ＝ma x (A T i ,j ,s ,０)㊀∀χi ,j ,s ,k ＝１a n d R i ,j ＝k m a x (A T i ,j ,s ,C T i ᶄ,j ᶄ,s ᶄ)㊀∀χi ,j ,s ,k ＞１χi ᶄ,j ᶄ,s ᶄ,k ＝χi ,j ,s ,k －１R i ,j ＝R i ᶄ,jᶄ＝k {ìîíïïïï(１３)㊀㊀㊀㊀㊀c s t i ,j ,s ＝s s t i ,j ,s ＋δi ,j ,s (１４)㊀㊀(４)各零件到达机器的时间约束.当一个子批中的所有零件均完成当前工序的加工后,这个子批才能被运输至下一道工序所对应的机器上:a t i ,j ,s ,r ＝０㊀㊀㊀㊀㊀㊀㊀∀j ＝１C T i ,j－１,s ᶄ＋ε㊀㊀∀j ＝１ξi ,j ,s ,r ＝ξi ,j －１,s ᶄ,r ＝１{{(１５)㊀㊀(５)各子批在机器上准备就绪时间.考虑可变子批划分时,同一个子批中各零件到达同一个机器上的时间不尽相同,因此当该子批中的所有零件均到达机器后,该子批才准备就绪:A T i ,j ,s ＝m a x ∀ξi ,j ,s ,r ＝１(a t i ,j ,s ,r )(１６)㊀㊀(６)各子批及零件的开始加工时间约束.当子批在机器上准备就绪且该机器处于空闲状态时,则该子批可以开始加工,同一个子批中的各零件按照到达时间先后顺序依次开展加工:㊀㊀S T i ,j ,s ＝ma x (A T i ,j ,s )㊀㊀∀χi ,j ,s ,k ＝１a n d R i ,j ＝k m a x (A T i ,j ,s ,C T i ᶄ,j ᶄ,s ᶄ)㊀∀χi ,j ,s ,k ＞１χi ᶄ,j ᶄ,s ᶄ,k ＝χi ,j ,s ,k －１R i ,j ＝R i ᶄ,jᶄ＝k {ìîíïïïï(１７)s t i ,j ,s ,r ＝S T i ,j ,s ㊀㊀∀ηi ,j ,s ,r ,x ＝１c t i ,j ,s ,r ᶄ㊀㊀∀ηi ,j ,s ,r ＞１ηi ,j ,s ,r ᶄ＝ηi ,j ,s ,,r －１{{(１８)ηi ,j ,s ,r ＞０㊀㊀㊀㊀㊀㊀i f ξi ,j ,s ,r ＝１ηi ,j ,s ,r ɤw i ,j ,s ㊀㊀㊀㊀i f ξi ,j ,s ,r ＝１ηi ,j ,s ,r ᶄ－ηi ,j,s ,r ＜０㊀㊀i f a t i ,j ,s ,r ＞a t i ,j ,s ,r ᶄξi ,j ,s ,r ＝ξi ,j ,s ,r ᶄ＝１{|ηi ,j ,s ,r ᶄ－ηi ,j ,s ,r |＞０㊀i f a t i ,j ,s ,r ＝a t i ,j ,s ,r ᶄξi ,j ,s ,r ＝ξi ,j ,s ,r ᶄ＝１{üþýïïïïïïïï(１９)㊀㊀(７)各子批及零件的结束加工时间约束.当子批中最后一个零件完成一道工序的加工后,该子批才结束该工序的加工:c t i ,j ,s ,r ＝s t i ,j ,s ,r ＋δi ,j ,s ＋πi ,j ㊀㊀∀ηi ,j ,s ,r ＝１s t i ,j ,s ,r ＋πi ,j ㊀㊀㊀㊀㊀∀ηi ,j ,s ,r ＞１{(２０)C T i ,j ,s ＝c t i ,j ,s ,w i ,j ,s (２１)２㊀求解算法本文所建立的混排可变分批作业车间多目标调度优化模型作为作业车间分批调度问题的一个扩展,属于典型的N P Ｇh a r d 问题.基于分解的多目标进化算法(m u l t i Ｇo b j e c t i v eo pt i m i z a t i o ne v o Ｇl u t i o n a r y a l g o r i t h m b a s e d o n d e c o m po s i t i o n ,MO E A /D )是一种基于群体智能的启发式优化算法,通过采取特定的分解策略,可有效提高它在多目标优化问题尤其是高维多目标优化问题上的收敛性[１Ｇ２].MO E A /D 常用的分解策略包括权重聚９７５１ 基于多目标混合进化算法的作业车间混排可变分批节能调度方法谢法吾㊀李玲玲㊀李㊀丽等合法㊁基于惩罚的边界交叉聚合法和切比雪夫法.本文采用基于切比雪夫法的MO E A /D 算法.将分解策略应用于MO E A 算法中虽能有效提高算法收敛效率,但容易导致一个解出现在多个邻域中进而降低种群多样性[１６].J a ya 算法是２０１６年被提出的一种新的元启发式算法,通过采用J a ya 种群更新机制以提高解的多样性和分布性[３,１０].鉴于此,本文将J a ya 算法的种群更新机制与MO E A /D 算法结合,以进一步协调算法的全局搜索与局部搜索性能.本文提出的改进多目标混合进化算法(MO J A /D )的流程如图１所示.下面将详细介绍算法的关键步骤,包括编码方式㊁种群初始化㊁基于J a y a 的解更新机制㊁局部搜索策略㊁交叉和变异操作等.图１㊀M O J A /D 算法流程图F i g ．１㊀T h e f l o wc h a r t o f t h e p r o po s e dM O J A /D ２．１㊀编码方式采用两级编码H ＝(X ,Y )表示可变子批划分方案和子批混排调度方案.２．１．１㊀可变子批划分方案编码采用X ＝[x i j ]I ˑN 表示可变子批划分方案编码.其中,x i j ＝[w i ,j ,１,w i ,j ,２, ,w i ,j ,s , ,w i ,j ,u i ,j ]表示第i 个工件在第j 道工序上划分的分批方案;u i ,j 为第i 个工件在第j 道工序上划分的子批总数;w i ,j ,s 为第i 个工件在第j 道工序上的第s 个子批的批量大小.图２展示了３个工件分别在３道工序中的分批方案.其中,x ２２＝[２,４,４]表示第２个工件在第２道工序上被划分成３个子批,各子批的批量大小分别为２㊁４㊁４.图２㊀工件分批方案示例(I ＝３,N ＝３)F i g ．２㊀A n e x a m p l e o f l o t s p l i t t i n g e n c o d i n gs c h e m e ２．１．２㊀子批混排调度方案编码采用Y ＝[y m ]１ˑQ 表示子批混排调度编码.其中,Q ＝ u i ,j 表示所有工件在所有工序上划分的子批总数;y m ＝(i ,j )表示一个子批,其中i 表示工件编号,j 表示工件工序编号;相同基因(i ,j )出现的频数o i ,j ,s 表示子批编号.以图３的染色体片段为例,各子批的加工顺序依次为(３,１),(１,１),(２,１),(３,２),(１,１),(３,１),(２,１),(３,２),(１,２),(１,３);其中,第一次出现的(３,１)表示第３个工件第一道工序上的第１个子批;第二次出现的(３,１)表示第３个工件第一道工序上的第２个子批.图３㊀子批混排调度方案的染色体片段F i g ．３㊀C h r o m o s o m e s e g m e n t o f s u b l o t s s e q u e n c i n ge n c o d i n g sc h e m e ２．２㊀种群初始化本文分别针对工件分批方案和子批调度方案设计了初始种群生成规则.２．２．１㊀可变子批划分方案的初始化采用文献[１３]中的工件分批方案初始化方法,具体如下:(１)随机初始化.在保证可变子批划分约束的条件下,随机生成子批数量以及各子批的批量大小,以保证种群的多样性.(２)平均初始化.首先随机生成第i 个工件在第j 道工序上的子批数量u i j ,然后根据下式确定各子批的批量大小:w i ,j ,s ＝[N i u i ,j]㊀㊀㊀㊀㊀㊀s ＝１,２, ,u i ,j －１N i － u i ,j －１s ᶄ＝１w i ,j ,s ᶄ㊀㊀s ＝u i ,j ìîíïïïï(２２)㊀㊀(３)混合初始化.将随机初始化与平均初始化方式结合,生成工件分批方案.２．２．２㊀子批混排调度方案的初始化采用典型调度规则[１７]生成子批混排调度０８５１ 中国机械工程第３４卷第１３期２０２３年７月上半月方案:(１)最多工序剩余的子批最先开始加工;(２)最长剩余加工时间的子批最先开始加工;(３)随机生成子批混排调度方案.２．３㊀基于J a y a的解更新机制J a y a种群更新机制的原理是在算法迭代过程中基于最优个体与最差个体的特征不断更新当前解,以提高解的多样性[３].根据可变分批调度问题特征,本文分别面向工件分批和子批调度方案设计了基于J a y a的解更新机制,具体如下.２．３．１㊀基于J a y a的工件分批方案更新采用可变子批划分策略时,同一个工件i在不同工序j上划分的子批数量u i,j不尽相同,由此导致算法迭代过程中产生的最优个体X b e s t㊁最差个体X w o r s t以及当前个体X n o w中的子批总数u i j也不相同.此时,若直接将当前个体X n o w与最差个体X w o r s t相同的基因舍弃并将X b e s t相应位置的基因赋值给X n o w,容易产生非可行解.鉴于此,设计了一种基于可变子批划分的J a y a更新操作,具体步骤如下:(１)从邻域中选择最优个体H b e s t和最差个体H w o r s t,取出对应的X b e s t和X w o r s t;在当前个体H n o w中取出X n o w;(２)初始化更新次数z＝０.若zɤZ,执行以下步骤:①随机选择工件编号i和工序编号j,若u b e s t i,jʂu w o r s t i,j,则进入步骤②;否则,进入步骤③;②若u n o w i,j＝u w o r s t i,j,则∀sɪ[１,u n o w i,j],更新w n o w i,j,s＝w b e s t i,j,s,进入步骤④;若u n o w i jʂu w o r s t i j,进入步骤③;③∀sɪ[１,m i n(u n o w i,j,u w o r s t i,j)],若w n o w i,j,s＝w w o r s ti,j,s,计算Δ＝w n o w i,j,s－w b e s t i,j,s,更新w n o w i,j,s＝w b e s t i,j,s,再随机选择一个子批编号sᶄɪ[１,u n o w i,j]且sʂsᶄ,更新w n o w i,j,sᶄ＝w n o w i,j,sᶄ＋Δ;进入步骤④;④更新zѳz＋１;(３)更新X n e w＝X n o w.图４a和图４b分别展示了u b e s t i,j＝u w o r s t i,j和u b e s t i,jʂu w o r s t i,j情况下的工件分批方案更新示例.(a)u n o w i,j＝u w o r s t i,j(b)u n o w i,jʂu w o r s t i,j图４㊀基于J a y a的工件分批方案更新示例F i g．４㊀J a y a u p d a t i n g m e c h a n i s mf o r l o t s p l i t t i n g２．３．２㊀基于J a y a的子批调度方案更新采用可变子批划分策略可能导致算法迭代过程中最优个体Y b e s t㊁最差个体Y w o r s t以及当前个体Y n o w编码长度不相同.同时,采用子批混排策略时,若直接将Y n o w与Y w o r s t在相应位置上相同的基因删除㊁并将Y b e s t相应位置的基因赋值给Y n o w,很可能出现非可行解.因此,针对可变子批划分和子批混排策略,设计了一种基于J a y a的子批调度方案更新方式,具体步骤如下.(１)从邻域内选择最优个体H b e s t和最差个体H w o r s t,取出对应的Y b e s t和Y w o r s t; (２)删除Y n o w上与Y w o r s t对应位置上的相同的编码,得到新的子批调度方案编码Y n e w; (３)删除Y b e s t上与Y n e w对应顺序上的编码; (４)将步骤(３)中的Y b e s t上剩余的编码按照顺序依次放入步骤(２)中的Y n e w上的对应位置; (５)进行编码合法性检查,移除多余编码,补充缺失编码;１８５１基于多目标混合进化算法的作业车间混排可变分批节能调度方法 谢法吾㊀李玲玲㊀李㊀丽等(６)输出Y n e w并结束.图５展示了基于J a ya 的子批调度方案更新示例.图５㊀基于J a y a 的子批调度方案更新示例F i g ．５㊀J a y a u p d a t i n g m e c h a n i s mf o r s u b l o t s e q u e n c i n g２．４㊀局部搜索策略根据混排可变分批调度问题特征,设计了三种局部搜索策略,包括面向工件分批方案的局部搜索㊁面向工件分批和子批调度方案的局部搜索以及面向子批调度方案的局部搜索.２．４．１㊀面向工件分批方案的局部搜索在不改变完工时间的前提下,设计了一种面向工件分批方案的局部搜索策略.该策略是基于子批合并方法,将同一台机器上相邻两个同一工件的子批合并,以减少子批数量由此降低子批运输能耗,如图６所示.工件分批方案局部搜索步骤如下:(１)初始化机床编号k ＝１.若k ɤK ,执行以下循环:初始化q ＝１;若q ＜m a x {χi ,j ,s ,k },执行以下循环:①提取机床M k 加工的第q 个子批编号F i ,j ,s (∃χi ,j ,s ,k ＝q )以及第q ＋１个子批编号F i ᶄ,j ᶄ,s ᶄ(∃χi ᶄ,j ᶄ,s ᶄ,k ＝q －１);②若i ＝i ᶄ,j ＝j ᶄ且Φk ,q ＋１＝０,将子批F i ,j ,s 与F i ᶄ,j ᶄ,s ᶄ合并为一个新子批,不改变该新子批中各零件的开始加工时刻和结束加工时刻;图６㊀基于子批合并的工件分批方案局部搜索F i g ．６㊀L o c a l s e a r c ho p e r a t o r o n l o t s p l i t t i n g③更新q ѳq ＋１.(２)输出X n o w结束.２．４．２㊀面向工件分批和子批调度方案的局部搜索为了进一步缩短机器空闲时间㊁减少机器空闲能耗,设计了面向工件分批和子批调度方案的局部搜索策略.该策略基于可变子批划分策略,尽可能地将完工时间较早的子批零件提前到机器空闲时段内加工,由此降低完工时间㊁减少机器空闲能耗.但是,子批拆分会导致子批数量增多进而增大子批运输能耗,如图７所示.向工件分批和子批调度方案的局部搜索步骤如下:(１)初始化机床编号k ＝１.若k ɤK ,执行以下循环:①初始化q ＝１;若q ɤm a x (χi ,j ,s ,k )且Φk ,q ＞０,进入步骤②;若q ɤm a x (χi ,j ,s ,k )且Φk ,q ＝０,进入步骤③;若q ＞m a x (χi ,j ,s ,k ),进入步骤④;②提取机床M k 加工第q 个子批的开始时刻Ω(２)＝S T i ,j ,s ,k (∃χi ,j ,s ,k ＝q );提取机床M k 加工第q －１个子批的结束时刻Ω(１)＝C T i ᶄ,j ᶄ,s ᶄ,k (∃χi ᶄ,jᶄ,s ᶄ,k ＝q －１);初始化l ＝q ,若q ɤm a x (χi ,j ,s ,k )],执行以下循环:a )确定χi ,j ,s ,k ＝l 所对应的子批编号F i ,j ,s ,提取该子批中的所有零件在前一道工序的完工时间Ωr ＝c t i ,j －１,s ᶄ,r ᶄ(∀ξi ,j －１,s ᶄ,r ᶄ＝１);b )∀r ɪ[１,w i ,j ,s ],若Ω(１)ɤΩr 且Ωr ＋πi ,j ɤΩ(２),将该零件编号放入集合B 中;c )若|B |＞０,将原子批F i ,j ,s 中出现在集合B 中的零件编号删除,并将该子批放到机床M k 上在时刻Ω(２)开始加工,同时将集合B 中所有零件合并为一个新子批并将其放到机床M k 上的空闲时间段[Ω(１),Ω(２)]内加工,更新X n o w 和Y n o w,更新q ѳq ＋２,结束循环并返回步骤②;反之,更新l ѳl ＋１;③更新q ѳq ＋１:④更新k ѳk ＋１;(２)输出X n o w 和Y n o w并结束.图７㊀基于子批拆分的工件分批方案和调度方案局部搜索F i g ．７㊀L o c a l s e a r c ho n l o t s p l i t t i n g a n d s u b l o t s e q u e n c i n g２８５１ 中国机械工程第３４卷第１３期２０２３年７月上半月２．４．３㊀子批调度方案局部搜索在不改变工件分批方案的前提下,采用文献[１８]中的基于关键路径的调度方案局部搜索策略,具体如下.局部搜索策略１:在关键路径中随机选择一个关键块,并将该关键块中的任意两个相邻子批工序互换顺序;更新子批调度方案Y no w.局部搜索策略２:在关键路径中随机选择一个包含三个及以上子批工序的关键块,将该关键块中首个子批工序或尾部的子批工序与其相邻的子批工序进行顺序互换,然后再将其余子批工序随机插入刚刚互换顺序的两个子批工序之间;更新子批调度方案Y no w.局部搜索策略３:在关键路径中随机选择两个关键块,其中一个关键块采用局部搜索策略１进行更新,另一个关键块采用局部搜索策略２进行更新;更新子批调度方案Y no w.２．５㊀交叉和变异操作在多目标进化算法中,采用交叉操作是为了保留有效的基因并将其传递给新生子代,而变异操作可有效提升种群的多样性.本文中,考虑可变子批划分和子批混排策略,分别设计了工件分批方案和子批调度方案的交叉操作㊁变异操作,介绍如下.２．５．１㊀交叉操作工件分批方案采用插入和交换方法[１]对工件分批方案进行交叉.其中,采用交换的交叉方法时,分别在两个父代染色体X 中随机选择一个x i j 并互换,如图８所示;采用插入的交叉方法时,首先在父代染色体X n o w中随机选择一个基因w i ,j ,s ,并将其从当前位置插入到x i j 中的其他任一位置.图８㊀工件分批方案交叉过程F i g ．８㊀C r o s s o v e r o p e r a t o r s o n l o t s p l i t t i n g㊀㊀子批调度方案的交叉采用P M X (pa r t i a l Ｇm a p pe d c r o s s o v e r )交叉方法[１９].首先选择交叉的起始和终止位置,然后将两个父代染色体Y n o w １㊁Y no w ２上的相应位置基因作互换,由此得到两个子代染色体Y n e w １和Y ne w ２.由于采用可变子批策略,可能导致两个父代染色体的编码长度不相同,再加上子批混排策略,使得两个父代染色体相应位置上的基因互换后产生非可行解.因此需对交叉后的两个新子代编码Y n e w １㊁Y ne w ２做合法性检查,移除多余的编码㊁插入缺失的编码.２．５．２㊀变异操作工件分批方案的变异,包括子批数量和子批大小的变异.其中,子批大小的变异,是在X ne w中随机选择一个子批大小w i ,j ,s ,再将其增加或减少一个随机数;子批数量的变异,是在X n e w中随机选择一个子批大小w i ,j ,s 并将其拆分为两个任意大小的子批,或者随机选择两个w i ,j ,s 和w i ,j ,s ＋１并将其合并为一个子批.图９展示了子批分批方案变异操作示例.子批调度方案的变异采用插入㊁交换方法[１１].即,在Y n e w 中随机选择一个子批并将其更换到其他任意位置,或在Y n e w中随机选择两个子批并将其位置互换,如图１０所示.３㊀试验结果与分析MO J A /D 算法采用P yt h o n ３．８编程,运行环境为２．２０G H zP C ,８G B R AM ,W i n d o w s １０,６４位操作系统,I n t e l C o r e i ５C P U .为了验证算法性能,选用L a ０１~L a １５(L a w Ｇr e n c e )共１５个算例,工件种类I ＝{１０,１５,２０},工序总数n ＝５,机器总数K ＝５.算例中相关参数设置如表２所示.３．１㊀参数设置采用正交试验设计确定最优算法参数.３８５１ 基于多目标混合进化算法的作业车间混排可变分批节能调度方法谢法吾㊀李玲玲㊀李㊀丽等。

改进迭代贪婪算法求解可重入流水车间调度问题可重入流水车间调度问题（reentrant flow shop scheduling problem）是指在多工序流水车间中，存在可重入现象的调度问题。

在车间中，每个作业需要按照一定的工序顺序加工，而每个工序都有不同的机器可以完成。

不同于一般流水车间问题，可重入流水车间问题允许同一作业在同一工序上重复进行，增加了调度的复杂性和难度。

迭代贪婪算法是一种常用于解决可重入流水车间调度问题的启发式算法。

它的基本思想是通过多次迭代，每次选择当前局部最优的决策来逐步优化最终调度结果。

然而，传统的迭代贪婪算法存在着一些不足之处，例如容易陷入局部最优解、收敛速度较慢等。

因此，本文将针对这些不足之处进行改进，以求更好地解决可重入流水车间调度问题。

一、改进之处在改进迭代贪婪算法求解可重入流水车间调度问题时，我们可以从以下几个方面进行改进：1. 变异操作策略的引入：传统的迭代贪婪算法只考虑选择当前局部最优解进行迭代更新，但这种策略存在着局限性。

我们可以引入变异操作策略，即在每次迭代中，按照一定概率引入一定程度的随机性，以避免陷入局部最优解。

通过引入变异操作，可以增强算法的全局搜索能力，提高算法的质量和效率。

2. 邻域搜索的扩展：邻域搜索是迭代贪婪算法中的关键步骤。

传统的迭代贪婪算法仅仅根据局部最优解进行邻域搜索，但这种策略可能无法充分探索搜索空间。

我们可以考虑扩展邻域搜索的范围，在搜索过程中引入一定程度的随机性，以增加解空间的探索度。

通过扩展邻域搜索的范围，可以更全面地搜索潜在解，提高算法的全局搜索能力。

3. 优化目标函数的定义：目标函数的定义直接关系到算法求解可重入流水车间调度问题的效果。

传统的迭代贪婪算法通常采用简单的目标函数，例如最小化总加工时间或最大化作业的完工时间。

然而，这样的目标函数并不能充分考虑到车间效率与资源利用率等因素。

我们可以重新定义目标函数，结合车间实际情况和约束条件，以综合考虑多个指标，从而求得更合理、更优的调度结果。