混合遗传算法在多目标柔性作业调度中的应用

　　1　引言

　　柔性作业调度问题[1](Flexible Job Shop Scheduling Prob-lem, FJSP)是指带有机器可选的多工艺路线的作业调度问题,它通常包含机器分配问题和工序调度问题。生产调度的目标也是多种多样的,可以根据调度目标的多少把调度问题分为单目标调度问题、双目标调度问题和多目标调度问题。

　　大多数文献研究的是以生产周期为目标的单目标调度优化问题。Ponnambalam等[2]研究了以生产周期、机床闲置时间和工件延误时间为目标的多目标调度优化问题。实际的调度大多是多目标的,传统调度中工件的加工路线是固定的,为了增加调度的灵活性,在工艺规划时可为工件设计多条工艺路线,调度时再根据生产情况选择最合适的一条工艺路线。Nasr等[3]的研究表明,为工件预留多条加工路线能有效地提高生产率和生产柔性。

　　到目前为止,已有一些传统的启发式算法求解FJSP优化调度问题[4, 5]。庞哈利[6]从集成化的角度研究了柔性JobShop计划和调度问题,建立了两层混合整数规划模型,并用遗传算法求解最佳加工路径,用启发式规则求解调度问题。

　　Alvarez-Valdes等人[7]提出了一个启发式规则,建模玻璃生产企业的生产调度为FJSP;Dimitr等人[8]从成本的角度优化调度,考虑了延迟成本和存储成本,提出了一个启发式规则,采用中心极限定理解决了调度中的竞争问题。

　　本文利用遗传算法良好的全局搜索能力和禁忌搜索具有记忆能力的全局逐步优化特性,将两种算法进行混合,针对车间流控制系统中的柔性作业调度问题进行研究,利用层次分析法求解各个目标的权重,利用线性加权和公式把多个目标函数值映射为染色体的适应度。通过混合遗传操作,得到符合要求的最优解或近优解。

　　2　数学模型

　　本文的FJSP调度问题描述如下:n个工件在m台机器上加工,已知各操作的加工时间、生产费用和各工件在各机器上的加工次序约束,要求确定与工艺约束条件相容的各机器上所有工件的加工开始时间、完成时间和加工次序,使生产周期、生产成本、设备利用率加工性能指标达到最优或次优。

　　其中生产周期目标用工件的最大完成时间度量;生产成本目标用所消耗的加工成本以及在制品存储成本度量;设备利用率目标用机器的总负载和最大负载度量。

　　目标函数及约束条件如下:

　　3　混合遗传算法(GATS)

　　本文所解决的问题属于典型的NP难题,近年发展起来的遗传算法对该类问题的求解具有较为显著的优势。遗传算法的优越性主要表现在搜索过程中不易陷入局部最优,即使在所定义的适应度函数不连续的情况下,也能以极大的概率找到最优解。然而,与传统的启发式算法相比,遗传算法不适用于邻域最优解的微调结构,运算效率低。本文把禁忌搜索算法嵌入到遗传算法中,这种混合结构由于融入了禁忌搜索法的思想,使得那些只有通过禁忌检验的个体,才能真正地被作为新的个体所接收,这一方面使得那些有效基因缺失、但适宜度不高于其父代的个体被禁忌掉,另一方面,也使得那些包含有有效基因、但适宜度较低的个体有更多的机会参加交叉和变异,从而延缓或避免了早熟收敛的发生,也提高了遗传算法的爬山能力。