务ｌ造 訇 出 基于交替迭代遗传算法的成批车间生产计划与调度 的集成优化 Ａｌｔｅｒｎａｎｔ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｎｔｅｇｒａｔｅｄ ｂａｔｃｈ ｐｒｏｄｕｃｔｉｏｎ ｐｌａｎｎｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ ｏｆ ａ ｋｉｎｄ ｏｆ ｊｏｂｓｈｏｐ 熊福力 ，严洪森 ＸＩＯＮＧ Ｆｕ．¨１。＿．ＹＡＮ Ｈｏｎｇ．ｓｅｎ ｌ １（１．东南大学自动化学院，南京２１ ００９６；２．复杂工程系统测量与控制教育部重点实验室。南京２１ ００９６） 摘要：研究了一类零部件混批生产车间需要加工准备的多周期成批生产计划与调度的集成优化问 题，建立了生产计划和调度集成优化的非线性混合整数规划模型。并提出了一种交替式混合 遗传协调优化算法求解该集成优化问题。其主要思想是给定计划用一混合遗传算法求调度， 反过来给定已求调度用另一混合遗传算法求取新计划，如此不断交替使用两个混合遗传算法 实现计划与调度的同时优化。仿真结果证明了该方法的可行性和有效性。 关键词；批量；作业车间调度；集成优化；交替迭代方法；遗传算法 中图分类号：ＴＢ４９１ 文献标识码：Ａ 文章编号：１ ００９－０１ ３４（２０１ １）５（下）－ｏｏ９５—０２ Ｄｏｉ：１ ０．３９６９／ｊ．１ｓｓｎ．１００９－０１ ３４．２０１１．５（下）．２８ ０引言 标过少，因此难以应用于实际，鉴于此，本文针对 生产计划与调度问题一直是生产运作与管理 有准备时间的多周期成批ｊｏｂｓｈｏｐ车间生产计划与 领域的研究热点，通常生产计划层和调度层是紧 调度的集成优化问题，给出了批量连续生产的工序 密联系的，处在不同层次的生产计划和调度都必 约束关系，为了解决求解时收敛速度较慢的问题， 须进行有效地沟通。生产计划与调度集成优化问 提出了一种交替迭代遗传算法来求解改模型。 题的求解方法目前主要有以下几类： １成：｝Ｅｊｏｂｓｈｏｐ车间生产计划和调度 １）采用递阶方法分层求解，即将生产计划递 的集成优化模型 阶分解为一系列不同的层次，然后采用一种自顶 本文研究的成批ｊｏｂ—ｓｈｏｐ车间生产计划与调 向下的方法由高层到低层依次作出决策Ｈ】。这种 度的集成优化问题可描述如下：在车间中有Ｍ台 递阶生产计划在过去一段时间内曾被认为是求解 设备，需要生产Ⅳ种零件，每种零件ｆ包含，ｚ，道 大型复杂计划问题的有效途径。但是由于忽略了 工序，每道工序必须在特定的一台机器上加工， 实际调度操作过程中的具体的能力约束而使得递 零件的加工工艺路线互不相同，该车间所生产的 阶分解的结果在实际生产过程中变得不可行。 产品具有种类多、数量大的特点，采用成批生产， ２）采用集成模型优化的方法，同时考虑不同 零件批量生产过程是连续不问断的。生产过程中 层次的约束条件，建立整体优化模型。在进行问 更换生产品种时需要不可忽略的准备时间。 题的求解时，有两种主要的求解方法：一种是整 综合考虑零部件生产费用、零部件库存费用 体法 ４Ｊ，对不同层次的所有决策同时进行处理。 和欠产惩罚费用、设备上加工任务的提前费用、 另一种是集成法 ’ ，同样针对整体的优化模型， 加班费用以及零部件加工准备工作费用。集成优 先对不同层次的生产计划分层求解，然后对不同 化目标函数可以表示成如下形式： 层次的优化结果进行协调和传递。 ｒ Ⅳ Ｍ 上述研究在求解集成优化问题的时候，往往很 ，＝ｍｉｎ｛ｙ￣∑［ ，＋ｃ ＋ｃ『 】＋∑∑ ｔ＝ｌ ｉ＝１ ｔ＝ｌ ｍ＝ｌ 难较快地得到满意解，模型往往过于简单，没有充 Ⅳ 珥 分考虑详细的工序约束关系或者考虑的集成优化目 （ ＋ ）＋∑∑∑（ ）） （１） 救稿日期：２０１１－０１－０７ 基盒项目：国家８６３计划现代制造集成技术专题资助项Ｎ（２００７ＡＡ０４Ｚ１１２）；国家自然科学基金资助项ＩＮ（６０９３４００８，５０８７５０４６） 作者简介：熊福力（１９７４一），男，黑龙江肇东人，博士生，主要从事制造系统的生产计划与调度建模和智能优化算法等 研究工作。 第３３卷第５期２０１１－５（下） 【９５】 务ｌ 匐 出 生产平衡约束考虑产品库存量、产品需求量 和计划生产量之间的平衡关系 ＡＩＨＧＡ算法和ＭＯＨＧＡ算法的性能比较，所有算 例都由软件采用随机的方式自动生成。为方便比较， ２种算法中所用遗传算法的交叉率均取为０．９，变异 Ｉ 一Ｉ ＝Ｉ＋‘ｌ 一１ ＋Ｘ／ｔ—ｄ／ｔ ｆ＝ｌ，２，…，Ｎ 同时有非负约束： ≥０， ≥０， ≥０， ｔ＝１，２，…，Ｔ （２） 率均取为０．１。以设定的最大运行时间为终止条件。 实验结果中可以看出，在相同运行时间下， 从ＩＴＥＲＧＡ获得的目标函数值平均比ＣＯＮＴＧＡ的 要小１５４％，同时也说明本文提出的集成优化方法 能够较快地收敛到一个满意解。 Ｖｉ＝１，２，…，Ｎ；ｔ＝ｌ，２，…， （３） 由于零件在做好准备工作之后才能开始加工，有 ＞ ＋ ｒｌ７ （４） 要保证批量为连续生产，应该满足下述工序 约束： １）当Ｐ ｌ＞Ｐ“时 ， ｌ， ｆ， １， ．ｌ≥ 竹 ， ， （５） ２）当 ｌ＜Ｐｆｆ时 ，儿 ， １， １≥ 百ｉＪ，ｉ，厂卜ｐ ｌ－＿ｐｉ， １（Ｘｉｌ＿１）（６） ＝１一 ， （Ｈ） （７） 同时有工件加工顺序约束： ｏｉｊ｜＋ｔｔ ｊ＿ｌ ＋ｐ Ｘｎ＋ｆｉ＇ｊ＇ｔｒｉ－ｆ《ｓｔ ｆ ｉｊ，ｉ Ｊ Ｉｍ，０８、 利用调度约束来细化设备负荷约束有： ｍａｘ｛％＋ｆ ＋ｐｌｉＸ 十△ ｐｍｔ一厶 ｐ ：ｐｍｔ ｉＪ∈Ｙｍｔ ９１ ２模型算法及算例 为了有效地求解上述集成优化模型，本文研究 了一种交替式迭代遗传算法（ＡＩＨＧＡ）。该算法的 工作流程如下： 步骤１：采用混合遗传算法求解粗计划模型 得到初始生产计划。 步骤２：以初始生产计划作为约束，采用另 一混合遗传算法寻找集成优化模型的一个可行调 度排序，作为初始调度。 步骤３：以上一步得到的调度顺序作为约束， 采用生产计划层混合遗传算法来优化生产计划。 步骤４：以上一步得到的生产计划作为约束， 采用调度层遗传算法来优化调度顺序。 步骤５：如果满足算法终止条件，则停止， 输出结果；否则，转步骤３。 上述混合交替迭代遗传算法已经用Ｍａｆｌａｂ７．０ 实现，为了说明该算法的计算效果，这里给出一种 计划调度同时优化遗传算法（ＭＯＨＧＡ）做比较， 其基本思想是将计划解和调度解编码到同一染色体 上，采用选择，交叉和变异等操作同时优化生产 计划和调度。表１是不同算例情况下本文提出的 ［９６１ 第３３卷第５期２０１１－５（下） 表１ ＩＴＥＲＧＡ和ＣＯＮＴＧ时算性能的比较 垦 Ｐａｒｔｓ×Ｏｐｅｒａｔｉｏｎｓ Ｘ Ｆａｃｉｌｉｔｉｅｓ 时间（ｓ） 改善率 ３结论 本文研究了一类零件加工有准备时间且为批量 生产的ｊｏｂ ｓｈｏｐ车间多周期生产计划和调度的集成优 化问题，建立了该类问题的非线性混合整数规划模 型，并给出了一个交替式迭代集成优化方法。由于该 模型的复杂性并考虑到遗传算法在求解大规模复杂 组合优化问题时表现出的优越性，文中提出了一种 混合交替迭代遗传算法（ＩＴＥＲＧＡ）用以求解该类问题。 这相当于在在生产计划和调度求解两个过程之间加 一个循环迭代过程，将递阶算法构成一个闭环系统， 提高了求解速度，文中给出的大量算例的数值实验 中，ＩＴＥＲＧＡ方法所获得的平均目标值比ＣＯＮＴＧＡ 的要小１５Ａ％，具有较快的求解速度和精度。 参考文献： ［１】ＢｏｗｅｒｓＭＲ，Ｊａｒｖｉｓ ＪＥＡｈｉｅｒａｒｃｈｉｃａｌｐｒｏｄｕｃｔｉｏｎｐｌａｎｎｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌ［Ｊ］Ｄｅｃｉｓｉｏｎ Ｓｃｉｅｎｃｅｓ，１９９２，２３（１）：１４４－１５９． ［２】Ｋａｒｉｍｉ Ｂ，Ｆａｔｅｍｉ Ｇ．Ｔｈｅ ｃａｐａｃｉｔａｔｅｄ ｌｏｔ ｓｉｚｉｎｇ ｐｒｏｂｌｅｍ：ａ ｒｅｖｉｅｗ ｏｆ ｍｏｄｅｌ ａｌｇｏｒｉｔｈｍｓ［Ｊ］．ｈＴｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，２００３，３１：３６５—３７８． ［３】张晓东，严洪森．一类Ｊｏｂ—Ｓｈｏｐ车间生产计划与调度的 集成优化【Ｊ］．控制与决策，２００３，１８（５）：５８１—５８４． ［４】何霆，刘文煌，梁力平．ＭＥＳ的计划、调度集成问题研究 ［Ｊ］．制造业自动化，２００３，２５（３）：２４—２６． ［５１ Ｌａｓｓｅｒｒｅ ＪＢ．Ａｎｉｎｔｅｇｒａｔｅｄｍｏｄｅｌｆｏｒｊｏｂ－ｓｈｏｐｐｌａｎｎｉｎｇａｎｄ ｓｃｈｅｄｕｌｉｎｇ【Ｊ】．Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９９２，３８（８）：１２０１－１２１１． 【６】尚文利，范玉顺．成批生产计划调度的集成建模与优化 ［Ｊ］．计算机集成制造系统，２００５，１ｌ（１２）：１１６３—１１６７．