基于智能优化算法的车间调度问题研究∗

袁亮，袁逸萍，冯欢欢，孙文磊

(新疆大学 机械工程学院，新疆 乌鲁木齐 830049)

0 引言

车间调度[1]是制造系统的一个研究热点，也是理论研究中最为困难的问题之一.调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路径、时间、机器和操作.

目前，对车间调度理论的研究已受到广泛的关注，并取得了较大的进展，但还很不成熟.其中，对调度问题的复杂性研究已成为工程背景很强的一个应用数学分支.在算法研究方面，基于知识的方法和算法技术相结合的趋势正变得日益显著，概率分析方法在算法效率和性能方面的研究也日渐增多.对于难以求得最优解的问题，给出多项式时间的搜索方法具有很大的现实意义，同样，算法的随机性能分析也是比较有效的分析手段.算法研究中，最优化性能的渐近性分析具有理论指导性，而基于启发式算法的误差估计来确定次优度则无疑同样具有很大的意义.

近年来，随着人们研究生产调度问题的复杂性越来越高，问题规模越变越大，鉴于精确算法的局限性，越来越多的学者把精力放在近似算法的研究上.近似算法由于其可在合理的时间范围内给出问题的近优或次优解而被广泛关注和研究，最典型的一类近似算法为启发式算法.启发式算法又可分为构造性启发式算法和元启发式算法.构造式启发式算法是根据问题信息或一组规则来对问题进行求解，这类算法往往能在较短时间内求出问题的近优解，其高效的运行速度是很多学者研究构造启发式算法的动力.最早的构造启发式算法是基于分派规则的算法，例如：1960年Gimer提出了一种优先分则框架.1977年Panwalker[2]总结了一百多种调度规则，著名的调度规则有最短作业优先加工(SPT)、先来先服务(FIFO)、最早交货期优先加工(EDD)等等.对调度规则的应用即有利用基本调度规则来求解的，也有利用基本调度规则的组合或加权组合来求解问题.Vepsalainen[3]针对加权拖期的调度问题提出了一组调度规则.金锋赫等[4]为了设计自动和手控设备混合的装配作业车间启发式调度算法，设计了装配作业和设备特性相结合的生产调度规则，经过在模具生产车间的仿真实验表明，所设计的组合调度规则对平均延期时间等目标具有好的优化结果.

迄今为止，计算复杂性理论表明，大多数调度问题都属于NP难题，目标解的搜索涉及解空间的组合爆炸.线性规划、动态规划、分支定界和梯度下降等传统方法，或是需要目标函数的特殊信息，或是复杂度大，或是优化性能差，因而一般只能处理小规模问题，难以高效高质量地求解复杂的调度问题.正是由于意识到基于计算和数值式的优化技术的弱点，以及调度问题的约束性、非线性、多极小性、不确定性、大规模性、多目标性等复杂性，人们努力研究和发展了统计式全局搜索技术和人工智能的方法，例如模拟退火、遗传算法、禁忌搜索、进化规划、进化策略、神经网络方法和混沌优化等.研究将这些优化算法应用于车间调度问题，已成为一个研究热点.

1 车间调度问题描述

车间调度问题可以描述为：设有N个工件在M台机器上加工，由于工件的加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题就是如何安排在每台机器上工件的加工顺序，使得某种指标最优.产品每道工序加工的机器号，用矩阵M表示，其中mij表示i产品的第j道工序加工的机器号.产品每道工序加工所需时间，用矩阵T表示，其中tij表示i产品的第j道工序加工所需的时间.具体满足下面条件：

(1)每一工件在机器上的加工顺序一定；

(2)每一台机器每次只能加工一个工件；

(3)每一工件在机器上的加工被称为一道工序，工序加工时间是固定的；

(4)工件在机器上被加工时不允许被打断；

(5)机器与工件可能开始时间都为0.

此例子运用遗传算法的具体设计，主要包括染色体编码设计、目标函数选择、遗传算子设计、参数选择等.约束条件如下：

（1）每件产品必须按规定的工序加工；

（2）每一台机器同一时间只能加工一个产品.

优化目标是安排每台机器上所应加工产品的加工顺序，使得在尽可能短时间内完成所有产品的加工任务.数学模型为：

Min（maxfi)

其中fij表示产品i第j道工序的完成时间，fi表示产品i的最终完成时间，tij表示产品i的第j道工序加工所需的时间，A(t)表示在t时刻正在被加工的产品集合，当产品在被机器j加工时yij=1，否则yij=0.

2 车间调度问题的智能优化算法研究现状

智能优化算法包括遗传算法、模拟退火算法、人工神经网络算法、蚁群算法、粒子群算法、人工免疫算法等.智能优化算法发展至今，已出现了各种不同的算法，不同的算法有不同的特点，在实际运用中采取何种算法，要根据具体所求解的问题的特点来选择.文章主要对模拟退火算法、遗传算法和蚁群算法给予介绍.

2.1 模拟退火算法

模拟退火算法[5]是近几年提出的一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效近似算法.它与以往的近似算法相比，具有描述简单，使用灵活运用广泛，运行效率高和较少受初始条件限制等优点，而且特别适合并行计算，因此不仅具有很高的实用价值，而且对推动并行计算的研究也有着重要的理论意义.

模拟退火算法最早见于IBM托马斯[6].J.沃森研究中心S.Kirkpatrick[7]等人的文章，他们在对组合优化进行研究后，根据迭代改进的思提出了“模拟退火算法”，模拟退火算法具有很强的局部搜索能力.模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温(即退火）使之达到能量最低点.反之，如果急速降温(即淬火)则不能达到最低点.加温时固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小.Metropolis准则，粒子在温度T时趋于平衡的概率为exp(−E/(kT))，其中E为温度T时的内能，E为其改变量，k为Boltzman常数.用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法.

2.2 遗传算法

遗传算法[7,8]是近年来迅速发展起来的一种全新的随机搜索与优化算法，其基本思想是基于Darwin的进化论和Mendel的遗传学说.该算法由密执安大学教授Hol2land及其学生于1975年创建.此后，遗传算法的研究引起了国内外学者的关注.1985年以来，国际上已召开了多次遗传算法学术会议和研讨会，国际遗传算法学会组织召开的ICGA会议和FOGA会议，为研究和应用遗传算法提供了国际交流的机会.遗传算法流程图（如图1）.

图1 遗传算法流程图

遗传算法主要通过交叉、变异、选择运算实现.交叉或变异运算生成下一代染色体，称为后代.染色体的好坏用适应度来衡量.根据适应度的大小从上一代和后代中选择一定数量的个体，作为下一代群体，再继续进化，这样经过若干代后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解.遗传算法中使用适应度这个概念来度量群体中各个个体在优化计算中有可能到达最优解的优良程度.

2.3 蚁群算法

蚁群算法[9]是一种本质并行的算法，它是根据蚂蚁群在外处在一个陌生环境寻找食物时，总是能找到一条最优路径而受到启示得到的.蚁群算法是由意大利学者M.Dorigo于20世纪90年代提出的一种启发式进行算法.蚁群算法流程图（如图2）.

用EDD（优先选择最早交货期的工件）、EODD（优先选择最早交货期的工序）、FCFS（优先选择服务先到达的工序）3种简单启发式调度规则的组合规则对此算例进行调度，使用相同的各参数：工件数N=4，机器数M=10，工人数W=7，所得的解为64 h.仿真得到的最佳生产周期的调度结果如图2所示.

图2 蚁群算法流程图

3 遗传算法在车间多目标智能调度优化中的应用

3.1 问题描述

本文研究的是受工人和设备双资源约束的柔性JSP调度问题，该调度问题可以描述为：W个工人在M台机床上加工N个工件，每个工件包含一道或多道工序，工件的工序顺序是预先确定的，但每个工件可能有一条或几条可行的加工路线，每道工序可以由不同的工人在多台不同的机床上加工，工序加工时间和加工费用随工人的技术水平和机床的性能不同而不同.工人的数量少于机床的数量，每一个工人会操作多台机床，工人的加工费用随其技术水平不同而变化.作业调度任务是制定出一个生产计划，该计划不仅要确定每个工件的具体加工路线、各机床上工序的加工顺序及操作机床的工人，而且要在满足约束条件的同时，使得生产周期、设备负载和生产费用指标取得最优值[8].

对工件、机床和工人有下面的约束条件：(1)每台机床一次只能加工一个工件，一个工件不能在同一台机床上加工多次；(2)各工件必须按工艺路线以指定的次序在机床上加工；(4)工序的加工时间是预知的，辅助加工时间被考虑到加工时间内；(5)工人可操作的机床集合是确定的，每个工人一次只能操作一台机床；（6）考虑工人操作机床的熟练程度.

3.2 种群初始化

为使初始种群最大限度地分布于解空间且尽可能产生较优良的个体，本文对初始种群部分个体的资源采用最短加工时间指配法，其余个体资源采用随机生成法.

以下是采用最短加工时间资源指配法生成部分种群的初始化步骤：

（1）令循环数k=1；

（2）将Chrom(k).z（Chrom为种群，z为个体，z=1,2,···Z）种群第一行置0；

（3）根据各工件i的工序数J，在Chrom(k).z的第一行随机寻找J个还未被占用的空位（0位），将i赋给该空位；

（4）从左到右遍历Chrom(k).z的第一行，计算各工件出现的序号，赋给Chrom(k).z的第四行；

（5）从左到右，根据各工件i及其工序号j，从可选机床集JmNumber中选择一个加工时间最短的机床号、并从可选工人集HmNumber中选择一个技术水平最高的工人号，分别赋给Chrom(k).z的第二行和第三行；

（6）令k=k+1；

（7）若k≤Popsize（种群规模），则转步骤2，否则退出循环.

采用随机生成法生成部分种群的方法步骤和以上采用最短加工时间资源指配法类似，区别于步骤5的是：从可选机床集JmNumber中随机选择一个机床号、并从可选工人集HmNumber中随机选择一个工人号.

3.3 遗传算子设计

3.3.1 交叉操作

为保证交叉后的个体仍是可行解，本文只对工序号进行交叉操作，而保存交叉前的机床号和工人号.

算法采用工件的集合分解法，既便于操作，又保证了同一集合中的工件在父染色体中与子染色体中具有相同的顺序.算法如下:

（1）随机选取几个工件放入集合s1，剩余的工件放入集合s2；

（2）令循环次数k=0；

（3）检查父染色体parent1工序链的第k个工序，如该工序属于集合s1，则进入子染色体offspring1.同样，检查父染色体parent2工序链的第k个工序，如该工序属于集合s2，则进入子染色体offspring1；

（4）k=k+1，如k小于染色体的长度，重复（3），否则进行步骤（5）；

（5）交换集合s1与s2，重复（2）、（3）和（4）.

3.3.2 变异操作

为确保变异后的个体也是可行的，变异操作采用分段方式，包括加工顺序变异、加工机床和工人变异.

（1）加工顺序变异

从种群中任意选取一个体，随机选择两变异点λ1，λ2，且λ1=λ2，交换λ1，λ2所在位置上的两工序号，为保证子代的可行性，保存变异前的机床号和工人号.

（2）加工机床和工人变异

针对在多台机床上由不同工人加工的工件i的工序号j的变异，为增大性能好的机床和操作能力强的工人的选中概率，采用轮盘赌选择方式重新从JmNumber中随机获取可用机床号，并从HmNumber中随机获取可用工人号，分别替换j对应的机床号和工人号.

3.4 实验仿真

此算例中仿真使用的各参数为：工件数N=4，机器数M=10，工人数W=7，种群个体数Z=50，迭代次数MAXGEN=100，选择概率GGAP=0.9，交叉概率Pc=0.8，变异概率Pm=0.1.对这批零件的加工过程重复仿真10次，得到的最优解或近似最优解为51 h.该调度结果只是较优解之一，调度人员可以根据车间实际情况从多个非劣解选择偏好解.

用EDD（优先选择最早交货期的工件）、EODD（优先选择最早交货期的工序）、FCFS（优先选择服务先到达的工序）3种简单启发式调度规则的组合规则对此算例进行调度，使用相同的各参数：工件数N=4，机器数M=10，工人数W=7，所得的解为64 h.仿真得到的最佳生产周期的调度结果如图3所示.

图3 启发式规则调度Gantt图

4 结论

智能优化算法的发展和研究对解决车间调度问题有重大的意义.合理的优化算法对改进车间调度有很大的帮助，不仅能够提高人与机器配合的效率，还能有效提高机器的利用率，从而为企业带来更大的利益.

车间调度问题是对于生产环境中复杂的、动态的多目标的一种抽象和简化.在对调度问题进行研究的方法上最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度不理想就是难以解决复杂的问题.因此，随着各种新的相关科学与优化技术的建立与发展，在调度问题上也出现了很大的进展.并且，以柔性车间调度问题为例，显示了遗传算法在解决受工人和机器双资源约束的柔性车间调度问题上的鲁棒性.

对车间调度问题的研究虽有几十年的历史，但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着很大差距.今后研究者可从以下几个方面进行深入的研究.进一步深入实际，找出车间管理与调度诸多因素的内部关系，建立最能反映生产需要的调度模型.进一步研究车间计划与车间调度之间的关系，建立计划与调度的集成模型，从整体上进行优化研究.进一步研究先进制造系统模式，探索快速实用的智能调度算法.总之，随着调度研究的深入，调度算法必然会进一步与生产实践相结合，向集成化、动态化、高效化、实用化、智能化的方向发展.