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

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

形¨ｊ学位论文

况下的最短延迟调度问题ｎ引。随后这类问题一直被作为研究的重点，１９７７年，ＬｅｎｓｔｒａＪＫ等人，１９７８年ＬａｗｌｅｒＥＬ，１９９１年，ＢｕｒｂｒｉｇｅＪＬ，１９９３年，Ｂｌａｚｅｗｉｃｚ等人，１９９８年，罗成新，赵玉芳等又从不同角度研究讨论了单机调度问题¨＂。

平行机调度问题是调度中重要的一类问题，其中包括不可中断时间表长问题，可中断时间表长问题及总完工时间问题。ｌ９６１，ＨｕＴＣ，１９６６，ＧｒａｈａｍＥＧ从不同方面对不可中断时间表长问题进行了深入的理论研究¨引。１９９７年，赵传立等人研究讨论了处理机具有不同开始加工时间的可中断调度问题，此外还有许多学者在这方面做了大量研究，这里不一一列举。

车间作业调度问题包括同顺序作业调度问题、自由作业调度问题和异顺序作业调度问题。这类也是研究中涉及最多的问题之一，另外，流水问题也是一类特殊的作业车间调度问题。１９６５年，针对ＪＳＳＰ问题，Ｌｏｍｎｕｃｋｉｎ训提出了分支定界法，其主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加型的约束缩小可行域；将原整数规划问题分支，分为两个子规划再解子规划的伴随规划，通过求解一系列子规划的伴随规划及不断的定界。最后得到原整数规划问题的最优解。１９６８年，Ｇｏｌｏｍｂ心们等人又提出了回朔法用来求解ＪＳＳＰ问题，它的思路是不断切割原问题规划的可行域，使它在不断缩小的过程中将原问题的整数最优解逐渐暴露且趋于可行域极点的位置。随后几年，车间调度理论主要围绕着整数规划、动态规划、分枝定界等这些方法进行，研究并解决了一系列有代表性的调度问题。

由于调度问题本身的复杂性，后来人们逐渐着手寻找更有效的求解方法，到６０年代后期，对于复杂的调度问题，人们开始研究用启发式方法加以解决，至此调度理论的主体结构基本建立起来。从７０年代开始，随着复杂性理论（ｃｏｍｐｌｅｘｉｔｙｔｈｅｏｒｙ）及ＮＰ一完全问题（ＮＰ．ｃｏｍｐｌｅｔｅ）研究的兴起，人们开始注意并重视调度问题的复杂性研究，证明了许多调度问题是ＮＰ难的（ＮＰ－ｈａｒｄ），即使简单的Ｊｏｂ．Ｓｈｏｐ和Ｆｌｏｗ．Ｓｈｏｐ问题也是ＮＰ难的，不存在有效的多项式求解方法，因此只好寻找有效的启发式方法来解决它们，针对不同的问题，人们提出了大量的启发式算法心２¨２３Ｈ２钉。到７０年代后期，对调度问题的研究深入，已作为一门应用数学分支，经典调度理论己逐渐成熟心５】【２引。主要侧重计算复杂性方面的研究，Ｌｅｎｓｔｒａ等心¨证明了３名允／Ｃｍａｘ，Ｊ２ＩＪ５３｝Ｃｍａｘ和Ｊ３ｌＪＳ２ＩＣｍａｘ三种情况都是ＮＰ难问题．Ｂａｌａｓ心引最早提出ＪＳＳＰ问题的Ｂ＆Ｂ算法，此后Ｃａｒｌｉｅｒ等他引基于Ｊａｃｋｓｏｎ∞们的剩余总加工时间最长（ＭＷＲ）规则提出预占先调度（ＪＰＳ）用来求解ＪＳＳＰ问题，并且取得了较好的结果．“

针对传统ＪＳＳＰ问题，以运筹学方法研究为解决问题的重点，即研究如何在ｍ台处理机床上安排ｎ个Ｊｏｂ的处理顺序和处理时间，以使某个目标函数（调度长度，拖期惩罚）极小化。调度长度极小的调度问题可用混合整数线性规划来求解，但由于约束和整数变量随着问题规模的增加而变得很多，所以只适合较小规模的调度问题。动态规划法隐含枚举整个空间的搜索方法，它把问题分解成若干步，然后在每步上搜索最优解它是求解小规模问题的有效算法但它