基于遗传算法的Job-Shop车间调度问题研究

【作者】 于竟；

【导师】 陈杰；

【作者基本信息】 南京理工大学 ， 管理科学与工程， 2008， 硕士

【摘要】 如何提高单件产品作业车间调度型(Job-Shop型)的生产制造效率是人们一直关注和希冀解决的问题。由于其计算复杂性、动态约束性等特点,Job-Shop车间调度问题已经被证明是一个NP(非确定性多项式)难问题,一直以来人们提出了各种智能算法和程序来加以解决,其中遗传算法作为求解该类问题的一种重要手段之一,得到越来越多国内外学者的重视。但是在这些研究和应用过程中,较慢的收敛速度和较低的求解准确度一直是这一研究的瓶颈。为了改善目前求解这类问题的遗传算法的性能,加快搜索最优调度解的速度,本文以某企业分厂模具制造车间为研究背景,从遗传算法的角度进行了Job-Shop生产方式下的车间调度算法研究。本文共分为三个部分:第一部分为基础理论部分(第一章),指出了论文选题的重要性,并对该课题的国内外研究现状进行了评述;第二部分为项目背景部分(第二章),对该项目企业分厂模具车间的生产环境、现状、计划控制流程以及生产特点进行详细阐述、分析与诊断;第三部分为算法分析部分(第三章、第四章),在基于工序编码方式的基础上,设计了保存基因片段逆序交叉的遗传算子,将其运用于基于模糊加工时间和交货期Job-Shop问题中,并通过经典理论算例和实际生产案例,验证了算法的有效性。研究结果表明:该遗传交叉方式不仅保证了遗传后代的可行性和多样性,而且提高了搜索最优调度解的准确度。更多还原

【Abstract】 How to improve the productivity under the Job-Shop manufacturing mode has always been an issue of concern to the people. Because of its complicated calculation, dynamic multi-restriction, Job-Shop scheduling problem (JSP) has been proved as NP-hard (Non-deterministic Polynomial-hard) problem, and many intelligent computation methods are introduced into this field in recent years. Among these, genetic algorithm (GA) is one of the most popular methods getting an increasing attention by domestic and overseas experts recently. But slow convergence and low precision still exist in these applications and research. To improve the performance of the existing GA for JSP and speed up searching for the optimal scheduling solution, based on the background of a mould manufacturing shop, this dissertation studied JSP using an improved GA.Three parts were contained:1. Chapter 1(basic theory), introducing the importance of the subject, the status of present worldwide research in this field.2. Chapter 2(project background), describing and analyzing the environment, status, and characteristics of production, the process of plan and control, etc.3. Chapter 3&4(algorithm analysis), based on operation-based representation, designing keeping-fragments-reverse-crossover, which was applied to JSP with fuzzy processing time and duedate, then classical and realistic numeric examples were given which validated the effectiveness and efficiency of the proposed method.The results showed that: this improved algorithm not only ensured validity and diversification of the evolving descendants, but also improved precision of optimal schedule.更多还原