工艺路线可变车间作业调度的杂合遗传算法-东南大学学报.PDF

第 卷第 期 ３０ ６ 东南大学学报（自然科 学版 ） Ｖｏｌ３０Ｎｏ６ 年 月 ２０００ １１ （ ） Ｎｏｖ．２０００ ＪＯＵＲＮＡＬＯＦＳＯＵＴＨＥＡＳＴＵＮＩＶＥＲＳＩＴＹ ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ  工艺路线可变车间作业调度的杂合遗传算法 陈伟达 达庆利 王 愚 （东南大学经济管理学院，南京 ２１００９６） 摘 要 针对工艺路线可变的车间作业调度，提出一种将遗传算法与启发式规则、模 拟退火法等有哪些信誉好的足球投注网站方法结合在一起的杂合遗传算法 通过对某双极型集成电路封装企 ． 业的车间作业调度仿真，结果表明它是有效和可行的． 关键词 车间作业调度；杂合遗传算法；模拟退火法；启发式规则 分类号 Ｏ２２３ 近年来，有关车间作业调度问题的研究大多集中在流水车间（ ）或加工车间（ ＦｌｏｗＳｈｏｐ Ｊｏｂ ［ ］ ）中１～３，然而，由于企业生产目的不同，生产形式也越来越多样化 除了一般的 Ｓｈｏｐ ． ＦｌｏｗＳｈｏｐ 和ＪｏｂＳｈｏｐ调度之外，还存在另外一种工艺路线可变的车间作业调度． 工艺路线可变的车间作业调度问题可以描述为：当多个工件在多台设备上加工时，其工艺 路线在加工前不能完全确定，即每个工件的加工工艺路线可能有几条，具体选择哪一条要由当 时的设备空闲情况而定． 本文针对工艺路线可变的车间作业调度问题的特点，提出了一种杂合遗传算法（ Ｈｙｂｒｉｄ ， ），并探讨了 中的交换和变异操作，论文最后结合某集成电路封装 ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓＨＧＡ ＨＧＡ 企业的调度问题，通过仿真，表明ＨＧＡ是有效和可行的． １ 工艺路线可变的车间作业调度问题的一般描述 工艺路线可变的车间作业调度问题可以描述为：个工件在 台设备上加工，工件 （ ｎ ｍ ｉｉ＝ （） ｊ ，，…，）的加工工艺路线为 （ ，，…， ），即每个工件的加工工艺路线可能有几条 １２ ｎ ｉ ｊ １２ Ｌ ． ＝ ｉ 作业调度的任务是适当安排工件的加工顺序，即确定各工件在各设备的加工开始时间，在满足 约束条件的同时，优化某些性能指标． 用于求解车间作业调度问题的常用方法有：分枝定界法、启发式方法和遗传算法等 分枝 ． ［］ ３ 定界法属于精确算法，利用分枝定界法