随着科学技术的发展,生产规模日趋扩大,复杂性越来越高,市场竞争也愈发激烈,这些对企业的管理和对生产过程的监控都提出了更高的要求。生产计划与调度是实施计算机集成制造系统的关键所在。科学家们已经利用运筹学中的线性规划、整数规划、目标规划和动态规划等方法,研究并解决了一部分有代表意义的调度和优化问题。但是由于更多的调度问题都是NP-困难问题,目前尚无有效的求解策略,因此针对调度问题的研究具有重要的理论意义和应用价值。企业的置换流水车间生产调度问题(Permutation Flow-shop Scheduling Problem,PFSP)是一类典型的NP-困难型生产调度问题,在流水车间中,由于同一台机器上要加工的工件可能有多个,一个工件可能有多道工序要到多台机器上加工,不同工序的加工时间也可能不相同,因此安排工件在机器上不同的加工顺序对最后的结果会影响很大。而最小化最大完成时间makespan的排序能够改进企业的准时交货能力,大大减少生产周转时间,对于在现有资源条件下提高工作效率和经济效益有着重要作用,这是目前现代集成制造系统CIMS极为关心的问题。本论文主要研究以makespan最小化为目标的PFSP问题。文中第二章对于研究该问题的各种方法作了分类和详细评述;第三、四章分析了该问题本身的特征知识,找出了一些开发启发式优化算法的有力工具;第五、六章在先前两章分析的基础上,研究了当前具有最好效果的NEH启发式优化方法,并对其进行了改进,实验证明改进的算法能够提高原有算法的性能,并且在解大规模流水调度问题中具有较好的效果。论文的主要贡献和创新包括如下内容:1.详细分析了几十年以来国内外学者对以makespan的最小化为目标的PFSP问题的研究,描述了该问题的研究进展,回顾和评述了解决该问题的各种优化方法。2.用栅格图来分析PFSP问题,利用新给出的垂直子路径和内部水平子路径概念,把Grabowski定义的关键块普通化和形象化;研究了路径以及路径长度的公式,给出了几种进行路径变换的方法,推导并扩展了各种不同情况下的下界公式;把单次关键路径构建和动态关键路径构建两种方法应用在NEH优化算法中,进一步证明了下界公式的有效性。3.除基本的算法外,研究了不同的计算makespan的方法并作了证明,给出了这些方法的适用范围,通过实验对其进行了验证。利用flow shop的可逆性质,一个排列的makespan可以用前向的完成时间和逆向的完成时间共同来表示。这样,在评估很多较为相似的排列时,可以尽可能多地利用中间结果,大大减少评估时间,增加算法的效率。在块插入的邻域搜索中,利用扩展的关键路径概念给出了评估此时相似排列makespan的快速计算方法。此方法相对于参考文献中的技巧,更为有效,能节省更多的时间。4.给出了多种解除NEH优化方法中ties的方法。综合考虑所能获得的最终解的质量和所花费的计算时间,几十年来NEH启发式一直是最好的算法。在NEH初始化排列的形成阶段和部分排列的构造过程中均存在ties,先前的研究中大都采用最自然的方式解除它们,而本文给出了42种不同的解除NEH中ties的方法。这些改进的算法中,大部分都相对于原始NEH有性能的上提高。此外,文中还给出了使用了ties解除方法之后算法所耗时间的变化,指出耗时并没有显著的增加。因此,这些改进后的算法都可以用来替代原来的NEH启发式,以便为其它的提高式启发式方法和元启发式方法提供更好的初始解。5.已有的NEH算法研究着重于初始化排列的形成阶段,本文将研究集中在对新工件的插入阶段。考虑到原算法中新工件的插入过程等同于邻域搜索,对于几种的精简的邻域与原NEH算法中的邻域作了比较分析,又给出了两种增强的邻域搜索方法,并取得了较优的结果。由于该较优的结果是建立在计算花费增加很大的基础上的,文中给出了几种节省时间的方法。最后,采用了一个精心设计的更为精简但更有希望的邻域,通过一个目标函数移除处在最差位置上的工件,然后将它插入更合适的位置,给出了性能更优的算法INEH以及在此基础上解除了NEH构造过程中ties的算法BINEH。同参考文献中的算法相比,它们具有较好的性能,并且其时间复杂度仅为O ( n~2m ),所以其最大的优势是在能得到较高质量的解的前提下,可以以很快的速度解更大规模的问题。