一类Flow+shop生产调度问题及其优化方法之分析与研究

《一类Flow+shop生产调度问题及其优化方法之分析与研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要随着科学技术的发展，生产规模日趋扩大，复杂性越来越高，市场竞争也愈发激烈，这些对企业的管理和对生产过程的监控都提出了更高的要求。生产计划与调度是实施计算机集成制造系统的关键所在。科学家们已经利用运筹学中的线性规划、整数规划、目标规划和动态规划等方法，研究并解决了一部分有代表意义的调度和优化问题。但是由于更多的调度问题都是NP．困难问题，目前尚无有效的求解策略，因此针对调度问题的研究具有重要的理论意义和应用价值。企业的置换流水车间生产调度问题(PermutationFlow．shopSchedulingProblem，PFSP)是一类典型的NP．困难型生产调

2、度问题，在流水车间中，由于同一台机器上要加工的工件可能有多个，一个工件可能有多道工序要到多台机器上加工，不同工序的加工时间也可能不相同，因此安排工件在机器上不同的加工顺序对最后的结果会影响很大。而最小化最大完成时间makespan的排序能够改进企业的准时交货能力，大大减少生产周转时间，对于在现有资源条件下提高工作效率和经济效益有着重要作用，这是目前现代集成制造系统CIMS极为关心的问题。本论文主要研究以makespan最小化为目标的PFSP问题。文中第二章对于研究该问题的各种方法作了分类和详细评述；第三、四章分析了该问题本身的特征知识，找出了一些开发启发式优化

3、算法的有力工具；第五、六章在先前两章分析的基础上，研究了当前具有最好效果的NEH启发式优化方法，并对其进行了改进，实验证明改进的算法能够提高原有算法的性能，并且在解大规模流水调度问题中具有较好的效果。论文的主要贡献和创新包括如下内容：1．详细分析了几十年以来国内外学者对以makespan的最小化为目标的PFSP问题的研究，描述了该问题的研究进展，回顾和评述了解决该问题的各种优化方法。2．用栅格图来分析PFSP问题，利用新给出的垂直子路径和内部水平子路径概念，把Grabowski定义的关键块普通化和形象化；研究了路径以及路径长度的公式，给出了几种进行路径变换的方

4、法，推导并扩展了各种不同情况下的下界公式；把单次关键路径构建和动态关键路径构建两种方法应用在NEH优化算法中，进一步证明了下界公式的有效性。3．除基本的算法外，研究了不同的计算makespan的方法并作了证明，给出了这些方法的适用范围，通过实验对其进行了验证。利用flowshop的可逆性质，一个排列的makespan可以用前向的完成时间和逆向的完成时间共同来表示。这样，在评估很多较为相似的排列时，可以尽可能多地利用中间结果，大大减少评估时间，增加算法的效率。在块插入的邻域搜索中，利用扩展的关键路径概念给出了评估此时相似排列makespan的快速计算方法。此方法

5、相对于参考文献中的技巧，更为有效，能节省更多的时间。4．给出了多种解除NEH优化方法中ties的方法。综合考虑所能获得的最终解的质量和所花费的计算时间，几十年来NEH启发式一直是最好的算法。在NEH初始化排列的形成阶段和部分排列的构造过程中均存在ties，先前的研究中大都采用最自然的方式解除它们，而本文给出了42种不同的解除NEH中ties的方法。这些改进的算法中，大部分都相对于原始NEH有性能的上提高。此外，文中还给出了使用了ties解除方法之后算法所耗时间的变化，指出耗时并没有显著的增加。因此，这些改进后的算法都可以用来替代原来的NEH启发式，以便为其它的

6、提高式启发式方法和元启发式方法提供更好的初始解。5．已有的NEH算法研究着重于初始化排列的形成阶段，本文将研究集中在对新工件的插入阶段。考虑到原算法中新工件的插入过程等同于邻域搜索，对于几种的精简的邻域与原NEH算法中的邻域作了比较分析，又给出了两种增强的邻域搜索方法，并取得了较优的结果。由于该较优的结果是建立在计算花费增加很大的基础上的，文中给出了几种节省时间的方法。最后，采用了一个精心设计的更为精简但更有希望的邻域，通过一个目标函数移除处在最差位置上的工件，然后将它插入更合适的位置，给出了性能更优的算法INEH以及在此基础上解除了NEH构造过程中ties的

7、算法BINEH。同参考文献中的算法相比，它们具有较好的性能，并且其时间复杂度仅为O(n2m)，所以其最大的优势是在能得到较高质量的解的前提下，可以以很快的速度解更大规模的问题。索关键词：生产调度，最大完成时间，关键路径，启发式，邻域搜ABSTRACTWiththedevelopmentofscienceandtechnology,theproductioncomplexityofenterprisesincreasedgreatly,andthecompetitionbecamemoreandmorefiercer,SOthemanagementonthefa

8、ctoriesandthemonito