基于改进遗传算法的混合车间调度问题研究1(9)

基于改进遗传算法的混合车间调度问题研究

基】‘改进遗传算法的混合下问生严测发问题研究

业，即被加工完的作业阻塞在上流机器上。这就是零缓冲区。

删，：不等待限制只能出现在流水作业中。

陀伽：循环指可以出现在异序作业环境，它表示作业可以多于一次的访问同一处理机。

＇，域表示要优化的目标函数，它可以是

Ｃｍ。：时间表长，表示最后一个被加工完任务的完工时间。

ｋ瓤：最大延误时间。

∑ｑ，∑％ｑ：总完工时间，加权总完工时间。

∑ｑ，∑一ｑ：总误工，加权总误工。

∑ｑ，∑＿ｑ：误工任务数，加权误工任务数。

１．２．２调度问题国内外研究现状

１９世纪末２０世纪初，内燃机的广泛应用引发了制造业的变革，制造业进入了以兵器工业和汽车制造业为代表的大批量生产时代，出现了流水生产线，２０世纪２０至４０年代制造业出现了机群式生产模式阳１，但在当时，生产调度主要依靠经验进行，没有自成体系的理论支撑。自２０世纪５０年代初期，应用数学、运筹学、工程技术等领域的学者才开始对制造过程中的调度问题进行大量研究。在研究的初期阶段，调度问题是作为一个纯粹的数学问题加以研究，５０年代早期，针对ＦＳＳＰ（流水车间调度）问题，Ｓ．Ｍ．Ｊｏｈｎｓｏｎ【ｌ们提出了解决ｎ／２／Ｆ／Ｃｍａｘ（ｎ个工件２台机器的Ｆｌｏｗ．Ｓｈｏｐ型调度的最小流程周期问题）和部分特殊的ｎ／３／Ｆ／Ｃｍａｘ问题有效的Ｊｏｈｎｓｏｎ规则，虽然只是针对流水作业的求解２谳ｍａｘ，Ｊ２方法，但它对以后的研究有很大的影响．此后相继有利用多项式时间算法求解

ｌＪｓ２ＩＣｍａｘ和Ｊ２ＩＴｉ－１ＩＣｍａｘ等特殊的ＪＳＳＰ（作业车间调度）

问题，这些研究奠定了经典调度理论的基础，标志着调度理论研究的开始。

最早的调度问题是单机问题，同时也是最简单的调度问题。首先单机调度问题比较容易求出解决方案，这些方法对于研究比较复杂的调度问题具有指导作用，可以为处理复杂调度问题提供近似算法；１９５５年，ＪａｃｋｓｏｎＪＲ针对生产线上单机调度问题的最小延缓时间做了深入的研究，提出了分派规则ｎ１Ｊ。１９５６年，ＳｍｉｔｈＷＥ对基于多最优的单阶段生产调度问题进行了研究ｎ引。１９７３

Ｅ年ＬａｗｌｅｒＬ研究了具有优先约束的单机最优调度，讨论了加权总完工时间

最小的优先调度规则ｎ引。１９７４年，Ｂａｋｅｒ对单机作业情况下工期和最早开工时间最小延迟调度问题进行了详细论述ｎ劓。１９７５年，ＭｃＭａｈｏｎ等讨论了具有准备时间和完工日期最短的调度问题ｎ５１，１９７６年，ＬａｇｅｗｅｇＢＪ等人研究了单机情