一种改进的贪心遗传混合算法在车间调度中的应用与研究 李辰
【期刊名称】《《电子测试》》
【年(卷),期】2013(000)006
【总页数】3页(P141-143)
【关键词】遗传算法; 贪心算法; 车间调度
【作 者】李辰
【作者单位】大连交通大学软件学院 116052
【正文语种】中 文
【中图分类】TH164
0 引言
作业车间调度问题是困难的组合优化问题，它是一类满足任务配置和顺序约束要求的资源分配问题。车间作业调度作为CIMS体系结构中连接生产控制层和生产计划的中间环节，在两方面的发挥着重要作用：一方面接受计划决策信息，在资源形成具体生产实施方案和时间和空间上合理配置任务，驱动整个生产系统高效运作，是计划实现的保证；另一方面，通过统计分析，有机协调整个生产系统，接受生产过程的实际信息，并向决策层反馈计划执行情况。目前为止，车间调度问题的研究日益深入。从静态调度到动态调度，从最初的单机调度发展到多机调度，从确定性调度到随机性调度等。本文提出了一种将贪心算法融入遗传算法中的一种混合遗传算法，以提高求解质量，通过算例分析，可以看出本文提出的混合遗传算法有显著优势。 1 车间调度问题概述
车间作业调度问题是一类典型的实际生产调度问题的简化模型,它是一个典型的NP难问题,同时也是最有名的复杂组合优化问题之一,因此对其研究具有很重要的理论意义和工程价值。目前解决车间调度问题的方法主要分为两大类,有精确算法和近似算法两类,精确算法主要包括拉格朗日松弛法、分支定界法、基于析取图模型的枚举方法等,近似算法包括优先权
规则调度算法、邻域搜索算法、瓶颈转移启发式算法和人工智能算法等。精确算法能够得到全局最优解,但是只适合解决小规模调度问题,对于大规模调度问题无实际应用价值。这些年来,邻域搜索算法相继应用于解决车间调度问题。其中,遗传算法由于其良好的全局搜索性能和内在的并行处理能力,越来越受到车间调度研究人员的关注,传统的遗传算法容易陷入局部最优收敛速度慢的状况,本人提出一种改进的遗传算法,对以最小工件完工时间和平均工件完工时间为目标的车间调度问题进行了研究。 2 车间调度问题的数学模型
车间调度问题 研究 n 个工件在 m 台机器上的加工。每个工件在各个机器上的加工次序和每个工件的各个工序的加工时间为已知，要求确定与约束条件相容的各机器上所有工件的加工开始时间，完成时间和加工次序，使加工性能指标达到最优。则 n个工件m 台机器的车间调度问题的一般性定义如下:
假设机器共有m个 (M1, M2, M3……Mm)，需要加工的工件一共有n个(N1, N2, N3……Nn)，Si表示工件Ni的工序数，工件Ni的加工工序为 Ni1m,Ni2m,Ni3m…… NiSim, 其中NiSim表示 工件Ni的第Si道工序是在第m个机器上加工，加工工时为Tij。
线型灯约束：
n0705
角度测量2.1 每个工件的每个工序的加工工时Tij为已知。
2.2 每个工件包扩一个由多道工序组成的工序集合，工件的工序顺序已知。
2.3 同一台机床仅能同一时间加工一个工件的一道工序。
2.4 不同工件的工序之间没有约束。相同工件工序满足先后顺序约束关系。
2.5 工序之间没有时间间隔。
2.6 各个工件的每到工序的开工时间大于或等于零，且一个工件的前一道工序加工完后才能进行下一道工序。
目标函数值为Min(Max{ C1, C2, C3,…, Cn}) Ci为工件Ni 加工时间。即第n个工件的最后一道工序的完成时间T，但是第n个工件的完工时间不一定是所有工件的最小完工时间，需要先求出每个工件每道工序在机器上的加工时间段，再从选定的加工机器依次计算每台机器最后的工件完成时间，取其中的最大值就是目标函数值。
3 改进的贪心遗传混合算法求解过程
编码问题是设计遗传算法的首要和关键问题。对遗传算法的编码技术必须考虑染体的合法性、可行性、有效性以及对解空间表征的完全性，对于车间调度也是这样。由于车间调度问题的组合特性以及
工艺约束性，染体的 Lamarkian 特性、解码的复杂性、编码的空间特性和存储量的需求是设计遗传算法编码通常要考虑的问题。
3.1.1 染体的 Lamarkian 特性。该特性考虑在所设计的编码技术下，染体的优点是否可通过一般的遗传操作传到后代种。如果后代通过遗传操作可有效继承父代的优点 ，则 称所采用的编码具有 Lamarkian 特性 ；若后代种不能够 从父代继承任何有用信息，则称所采用的编码不具有 Lamarkian 特性；若后代所继承的片段中只有部分与父代相同，则称所采用的编码具有半 Lamarkian 特性。鉴于遗传算法的优化机制，我们希望所设计的编码具有 Lamarkian 特性。自动启闭阀
3.1.2 解码的复杂性。就解码的有效性而言，我们希望 GA搜索用的码能够解码成活动调度，甚至搜索所采用的码跟活动调度一一对应。就解码复杂性而言，将不需要解码的相应编码归为0 类复杂性；通过简单映射关系实现解码的相应编码归为 1 类复杂性；通过简单启发式方法才能实现解码的相应编码归为 2类复杂性；只有通过复杂启发式方法才能实现解码的相应编码归为 3 类复杂性。
3.1.3 编码的空间特性。编码必须考虑码的可行性、所表征空间的完全性和冗余性。就可行性而言，编码空间通常分为两类：仅包含可行解的空间，可包含非法解的空间。就完全性而言，有的编码仅表征部分调度空间，而有的编码则可表征整个调度空间，就冗余性而言，有的编码使码与调度一一对应，而有的则是一到多或多到一的关系，这会影响解码和搜索的效率。
3.1.4 存储量需求。就 n个工件 m 台机器的 Job Shop调度问题而言，通常用码长来反映编码对存储量的需求。称 n ×m为 GA 染体的标准长度，即操作的总数量。基于此，可将编码分为三类：其一，码长等于标准长度；其二，码长大于标准长度；其三，码长小于标准长度。
用遗传算法求解车间调度问题，编码形式有以下几种：基于工序的编码，基于操作的编码，基于工件的编码，基于工件对关系的编码，基于先后表的编码，基于设备的编码，基于优先规则的编码，基于完成时间的编码，基于析取图的编码，随机键编码等。本文采用基于工序的编码，这种表达法将调度编码为工序的序列，每个基因代表一道工序。它有两种可能的方式来命名每道工序，一种自然的方式像TSP的顺序表达法是自然数来命名工序，但是因为车间调度问题是受加工路线的约束的，不是所有自然数组合都可以定义为可行的调度。另一种方式由Gen，Tsujimura和Kubot提出:给所有同一个工件的工序指定相同符号，然后再根据他们在给定染体中的出现顺序给以解释。对于由n个工件在m台机器上生产的问题，一个染体包括总共n x m个基因，每个工件出现在染体中的次数为m次，每个基因不表明一个工件的具体工序，而是指有上下依赖关系的工序。很容易看出任意的染体的排列总能产生可行调度。在图1中为一个3×3作业车间调度问题的编码示例方式。
图1 编码示例
3.2 适应度函数
Min(Max{ C1, C2, C3,…, Cn}) Ci为工件Ni加工时间。
3.3 选择算子
选择是遗传算法实现优胜劣汰的关键过程，为了保证当前种中的最优解被选择，同时不失种的多样性。本文采取贪心算法和适应度比例法两种方法结合，即：通过贪心算法将局部适应度最大的个体直接选择到下一代，再通过适应度比例法选择出下一代种的个体。
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。在选择算子中引入贪心算法，可以加快算法的收敛速度。
贪心变换方法可以看做是一种算子。在算法每一次迭代演化过程中，首先执行交叉算子和变异算子，接下来执行贪心算子，最后再执行选择算子，可以加快算法的收敛。
3.4 交叉算子
每一代的个体按一定的交叉概率交换其部分基因,能产生新的基因组合,并且使各个解有机会
海鲜机交流他们的优秀基因,可以获得比父代更好的解结构。根据本文所用的编码方式特点,使用了线性次序交叉,其方法步骤如下。
3.4.1 使用Random函数随机产生两个交叉位,根据交叉位的选取将每个父代染体分为三个子集分别为s1, s2, s3。
电厂生产管理系统3.4.2 交换两个父代中的s2。
3.4.3 在每个染体的初始基因位中依次删除已获取s2中的各基因,得子集s4。
3.4.4 将s4中的基因依次替代父代染体中的s1、s3对应的基因位。
4.4.5 重复以上步骤(1)～(4),得到所需要的新种。交叉概率控制交叉操作的使用频率,取交叉概率为0.3-0.8。
3.5 变异算子
遗传算法采用变换顺序的方法进行变异操作，即首先在个体中随机选择部分基因，再颠倒这些基因的顺序。但是，如果被交换的基因是最近的两个，变异操作产生的个体将同它的
父代个体一样。为了防止这种情况的发生，在变异操作中设定选取的基因块的数量不能少于2个，这样就可以避免无效变异操作的产生。变异操作的实现方法如下所述:
