研究一种基于改进遗传算法的车间调度问题
来源：UC论文网2015-12-27 22:56
导读:：作业车间调度是一类求解困难的组合优化问题，本文在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性，最终使算法能够趋于全局最优。在次基础上
论文关键词：遗传算法，车间调度，模拟退火
1. 引言
作业车间调度（Job Shop SchedulingProblem，JSSP）通常指车间生产过程的作业计划，解决如何合理地分配车间有限的资源，使资源利用率最高，成本最小等问题[1]。随着制造型企业之间竞争的加剧，调度决策水平的高低己经成为现代企业决定生产经营过程能否实现降低成本，对市场实现快速响应，从而实现稳定高效地运转的决定性因素之一。为提高调度水平，新的生产调度策略和优化算法不断被提出并被研究，以提高资源的利用率及操作管理的水平，生产出更具有竞争性的产品。因车间调度优化问题在提高生产效率，降低生产成本等方面至关重要，所以车间的调度优化工作成为现代企业制造中的重要研究课题之一。
2. JSSP问题的数学描述
JSSP问题可以描述为如下：
1）一个工件不能两次被同一机器加工；
2）不同工件的加工工序之间没有先后约束；
3）工序一旦进行不能中断；
4）每台机器一次只能加工一个工件；
5）下达时间和交货期都不是确定的。
问题的数学描述为：
（1） 
：机器
先于机器
加工工件
，
，
（2）工件
先于工件
在机床上加工
模拟退火，
，
（3）式中
，
， （4）其中，式(1)表示目标函数，式(2)(3)(4)表示工艺约束条件决定的各工件的各操作的先后加工顺序以及加工各个工件的各机器的先后顺序。式中，符号
和
分别为工件在机器上的完成时间和加工时间。3．用改进遗传算法(MGA)求解
3.1编码方式
如何将所研究问题的解转换为由编码形式表达的染色体是遗传算法的关键问题[2]。对JSSP问题，遗传算法的编码常见的有以下几种：基于工序(或操作)的编码、基于工件的编码、基于先后表的编码、基于工件对关系的编码、基于优先规则的编码、基于机器的编码、基于完成时间的编码、随机键编码、基于析取图的编码[3]。这些编码方法都存在这样或者那样的不足，鉴于以上车间调度问题编码方法所存在的问题，提出一个既能保证后代的合法性，又能表征全部解空间，解码又相对简单的编码方法很有必要。本文考虑一个基于工序(或操作)的编码[4,5]方法用来保证搜索空间是一个完整的解空间，并且任何操作者的所有交换可对应于合适调度，对于每个基因对应一道工序，代表该工序在进行调度操作时的处理优先级，对于n个工件m台机器的调度问题，一个染色体由
个基因组成。考虑3个工件和2台机器问题的机器加工次序矩阵：
以及加工的时间矩阵：
假设一个任意基于操作的解分别为s = (1，3，2，2，1，3)， 其中1，2和3分别代表工件1，2和3范例。通过一个半活动解码过程[4,5]，工件的加工次序对于机器1对应3-2-1，对于机器2对应1-2-3。它们对应的makespan(工件完工时间)为7的甘特图如图１所示：
Figure 1. Halfactivities scheduling correspond to tmakespan
图1 半活动调度对应的makespan
我们认为，活动调度编码是半自主调度编码的一个子集，因此，最优调度方案必须是一个活动调度编码对应的工件完工时间[4]。活动调度编码的应用可以在下一个操作之前检查可能的空白的间隔时间所在最后位置模拟退火，并且在最后操作之前填补前一个空白间隔时间直到最后一个操作转化为半活动调度，导致makespan的长度可以变得更短。 因此，Gantt图(图1)被改变为如下图2所示，同时，对应的makespan 为6 (最优值)。
Figure 2. Activitiesscheduling correspond to tmakespan
图2 活动码调度对应的makespan
3.2解码算法
染色体只包含数字编码。在解码时首先要把基因与工序对应起来，即把优先级赋给对应的工序。
设：
——包含t个已调度工序的部分调度；
——阶段t可调度工序的集合对应给定的。解码步骤如下：
步骤1：令t=0，开始
为空的部分调度。初始的包括无紧前工序的所有工序。步骤2：比较
中所有工序的调度优先级，把具有最大优先级的工序(假设为
，其上道工序的结束时刻为
)尽可能早的加入到中，即从
时刻开始对该工序所对应机器上各加工空闲依次判断能否将此工件插入加工。若能，则在空闲中插入加工，并修改该机器上的加工队列；否则，把该工序加入到该机器加工队列的末尾，构造一个新的部分调度
。步骤3：按如下步骤更新数据集
： 从中删除工序
，通过在中增加工序的直接后续工序构造
，t=t+1。步骤4：返回步骤2直至构造一个完整的调度，由此得到的调度为活动调度。
3.3交叉，变异算子
交叉是最主要的遗传运算，遗传算法的性能在很大程度上取决于采用的交叉运算的性能，根据赌轮盘法[6]从父代群体中选择双亲，采用单点顺序交叉法生成后代。变异算子采用互换变异操作，随机从染色体中选择两个基因进行互换。
3.4选择算子
选择是遗传算法的推动力，采用扩大的采样空间，从双亲和后代种群中选择
个最优的个体作为下一代的双亲。并且增加记忆操作，把截止当前的最优解记录下来，在下次迭代中，若最优解优于该值，则替代之。运算结束时输出该值，即为寻得的最优解。3.5初始温度的确定
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一，初始温度高模拟退火，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，可节约计算时间，但全局搜索性能可能受到影响[7]。
初始温度可以用
估计，其中为充分大的数，
为目标函数的最坏情况
和最好情况
的差值，实际计算可以选
等值，此时对应的
0.9048,0.9512,0.9900等，已经达到充分大的要求，这里取
为所有工件所有工序加工时间之和；
为所有工件中所需加工时间最长的工件的加工时间，这是目标函数的两个可以估计的上下界，由此确定的初始温度可以保证是足够大的。3.6计算过程
车间调度问题是最小化问题，可以通过下边的方法直接将目标函数转化成适应度函数：
（5）计算步骤如下：
步骤1：初始化种群数目
，交叉概率
，变异概率
，退火速率
，输入机器顺序矩阵
,，加工时间矩阵
，计算初始温度
。步骤2：随机产生
个个体构成初始群体，并进行解码。令最优值
为当前种群的最优个体，
。步骤3：判断当前温度是否小于给定的终止温度，若是，结束；否则转步骤4。
步骤4：对种群进行交叉操作。
步骤5：对所有个体进行变异操作。
步骤6：对所有各个个体都进行定步长抽样的模拟退火操作，对旧个体采用swap方式产生新个体，以概率
接受后代。步骤7：保留原种群和产生的新种群中
个最好个体，及时更新。步骤8：令
，然后进行退火操作
，
并返回步骤3。步骤9：输出结果，并结束计算。
4. 实验结果与分析
为了测试上述所提出算法的性能，本文选取了Brandimarte基准问题和经典的Benchmarks基准问题模拟退火， Brandimarte基准问题包括工件数分别为（6，10，20），机器数为（6，10，5）的3个问题实例，Benchmarks基准问题包括工件数从10到30之间，机器数从5到15之间的8个问题实例在不同的范围的相同条件下的几个测试参数基准被选择，现采用文献[8]中提到的MT06， MT10和MT20的MGA的表现，和文献[9]中提到的LA01、LA06、LA11、LA16、LA21、LA26、LA31和LA36的LA类问题。
Table 1. Comparison of the MGA, SA, GA resulting dataof experiment
表1 比较MGA,SA,GA的计算结果
| 问题 | n,m | MGA | SA | GA |
| MT06 | 6,6 | 55 | 55 | 55 |
| MT10 | 10,10 | 930 | 939 | 997 |
| MT20 | 20,5 | 1165 | 1227 | 1247 |
| LA01 | 10,5 | 666 | 666 | 666 |
| LA06 | 15,5 | 926 | 926 | 926 |
| LA11 | 20,5 | 1222 | 1222 | 1222 |
| LA16 | 10,10 | 945 | 979 | 979 |
| LA21 | 15,10 | 1058 | 1083 | 1156 |
| LA26 | 20,10 | 1218 | 1253 | 1328 |
| LA31 | 30,10 | 1784 | 1784 | 1836 |
| LA36 | 15,15 | 1291 | 1321 | 1384 |
在同样的参数和终止标准的执行下，改进遗传算法(MGA)、简单遗传算法(GA)与模拟退火算法(SA)之间的计算结果见表1，从表1的结果来看改进遗传算法(MGA)的结果优于简单遗传算法(GA)与模拟退火算法(SA)。
5.结束语
车间调度问题已经证明为NP问题[10]，难以找到能够求得最优解的确定性调度算法。又由于遗传算法的优良特性，因此，采用遗传算法对车间调度问题进行求解已成为求解该类问题的趋势。本文提出的基于混合遗传算法的调度算法，同时融入模拟退火算法赋予搜索过程一种时变且最终趋于零的概率跳跃性，避免陷入局部最优并最终趋于全局最优。仿真实验表明了该改进遗传算法是可行的、有效的、具有较好的搜索能力。
参考文献:
[1]GERVEY M R,JOHSON D S,SOTHI R..The complexity offlowshop and jobshop scheduling[J].Mathematics and OperationsResearch1976(1):117-129．
[2]R. Cheng, M. Gen and Y. Tsujimura, “A tutorialsurvey of jobshop scheduling problems using genetic algorithms – I.Representation”, Computers and Industrial Engineering, 1976(30):983–997
[3]D. E. Goldberg, Genetic Algorithms in Search,Optimization and Machine Learning, Addison Wesley, New York, 1989.
[4]L. Wang and D. Z. Zheng, “An effective hybridoptimization strategy for job-shop scheduling problems”, Computers andOperations Research, 28, pp. 585–596, 2001.
[5]G. Shi, “A genetic algorithm applied to a classicjob-shop scheduling problem”, International Journal of Systems Science, 28(1),pp.25–32, 1997.
[6]Srinivas M,Patnaik L M.G enetic algorithm s:asurvey[J].C om puter,1994,27(6):17~26.
[7]B. Hajek, “Cooling schedules for optimalannealing”, Mathematics of Operations Research, 13(2), pp. 311–329, 1988
[8]J. F. Muth and G. Thompson, Industrial scheduling,Prentice Hall, Englewood Cliffs, NJ, 1963.
[9]S. Lawrence, “Resource constrained projectscheduling: an experimental investigation of heuristic scheduling techniques”,Graduate School of Industrial Administration, Pittsburgh, Carnegie Mellon University, 1984
[10]Blazewicz J, Finke G,Haopt G. New trends inmachine scheduling. European Journal of Operational Research, 1988; 37: 303—317
