【作者】 王晓娟；

【导师】 高亮； 李培根；

【作者基本信息】 华中科技大学 ， 工业工程， 2011， 博士

【摘要】 制造业是国民经济的重要组成部分。实际生产中的优化问题通常是多属性的,一般是对多个目标的同时优化,而且各个目标之间通常是不一致的,比如产品质量和生产成本往往是两个互相冲突的目标。此外,加工时间、完工时间和产品交货期等通常都是不确定的参数,实际生产过程中还存在着一些不确定的干扰因素,比如机器故障、原材料延迟到达、紧急订单的插入或者订单取消等突发事件,人们迫切需要对实际生产中的车间调度问题进行深入和广泛的研究,以更好地指导生产。本文正是在这样的背景下,结合实际生产调度问题所面临的多目标、参数不确定和动态性,对多目标柔性作业车间调度问题及其扩展进行了研究,并取得了一些有意义的研究成果。本文首先对单目标的柔性作业车间调度进行研究。将遗传算法“适者生存”进化准则融入禁忌搜索算法,将遗传算法的全局搜索能力和禁忌搜索算法的局部搜索能力相结合,提出了混合遗传禁忌搜索算法解决单目标的柔性作业车间调度问题。在遗传算法进化过程中,针对柔性作业车间调度问题的特点,设计了一种扩展的基于工序的编码及其产生活动调度的解码机制,并根据染色体的结构提出有效的交叉操作,IPOX交叉操作和一种新多点交叉操作MPX。对于遗传算法进化过程中产生的个体,应用禁忌搜索算法进行改进。将Balas和Vazacopoulos提出的邻域结构扩展到柔性作业车间调度问题,设计了禁忌搜索算法的邻域结构。运用提出的混合遗传禁忌搜索算法求解基准测试问题并与其他方法进行比较,验证了算法的有效性。根据现实制造系统中关注较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本等性能指标,建立了多目标柔性作业车间调度模型。在上述遗传算法的编码、交叉和变异等基本操作的基础上,提出了一种新的多目标遗传算法。在该多目标遗传算法里,采用了快速排序方法以提高算法构造Pareto最优解集的效率；采用了NSGA-Ⅱ的精英保留策略,并针对NSGA-Ⅱ在精英保留策略上的不足,引入了分布函数；此外,还采用了免疫和熵原理以维持进化种群的多样性。通过测试基准和模拟实际生产的算例,验证了算法的可行性和有效性；并利用层析分析法从一组Pareto最优解中选出最优妥协解。针对实际制造车间调度中,加工时间和交货期不确定的特点,本文结合模糊集的相关理论,建立了多目标模糊柔性作业车间调度模型。基于上述多目标遗传算法,求解了具有模糊加工时间和模糊交货期的多目标柔性作业车间调度问题,并通过算例测试,验证了算法的有效性。针对实际制造车间调度具有动态性的特点,提出了一种基于滚动窗口的动态调度优化策略,该策略采用基于周期和事件驱动的再调度机制将调度过程分成连续静态调度区间,在每个区间内用前面提出的多目标遗传算法进行优化调度。基于滚动窗口技术和多目标遗传算法,以交货期、最大流经时间、最大完工时间以及初始调度的偏离程度为性能指标进行同时优化。为了适应复杂多变的动态环境和保持生产的稳定性,提出了一种人机协同的调度机制。通过对算例进行测试,验证了该方法的可行性。在算法研究的基础上开发了多目标柔性作业车间调度原型系统,对原型系统的功能和效果进行了描述。最后,对全文所做的工作进行了总结,并对未来的研究方向进行了展望。更多还原

【Abstract】 Manufacturing sector is an important part and the main force of national economy. However, several objectives must be considered simultaneously in the real-world production situation and these objectives often conflict with each other. For an enterprise, different departments have different expectations in order to maximize their own interests. Moreover, as the international competition becoming more and more intense and the growing of personalized product demand by the market, process time, completion time, delivery time and so on in the real production have been unable to describe as determined parameters as they were used to be. Meanwhile, there may be some dynamic events, such as machine malfunction, late arrival of raw materials, emergency insertion or cancel of order and so on. In this situation, people need to research on scheduling problems under uncertainty immediately and wildly to guide the real production, not only the theory but also its application. In this background, combined with the uncertain and dynamic optimization problems in the real plant and production, main research of this thesis is about multi-objective flexible job shop scheduling problem. And some meaningful conclusions and results are pointed out from this research.The Flexible Job-shop Scheduling Problem (FJSP) is an extension of the classical job-shop scheduling problem (JSP). This paper presents a hybrid genetic algorithm and tabu search (GATS) which incorporates the principle of "the survival of the fittest" from genetic algorithm (GA) into tabu search (TS) to solve the FJSP. According to the characteristics of the FJSP, an extended operation-based representation which simultaneously describes the sequence of operations and the assignment of operations to machines is applied to represent solution for GATS, and solutions are constructed using a procedure that generates active schedules. Two effective crossover and mutation operators are proposed to adapt to the chromosome structure. After individuals of GA are obtained, TS is applied to improve these solutions. The neighborhood structures of TS are designed by extending proposition proposed by Balas and Vazacopoulos to FJSP. The hybrid algorithm is tested on a set of standard instance taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.An improved multi-objective evolutionary algorithm (MOGA) is proposed for solving the mulyi-objective FJSP. Firstly, the multi-objective FJSP optimization model is put forward, which the makespan, the mean flow-time, total tardiness, total workload of machines, workload of the critical machine and production cost widely concerned in complex manufacturing system are considered. In order to ensure convergence and the diversity of the solutions, an improved non-dominated sorting genetic Algorithm (NSGA-II) is proposed and the immune and entropy principle is used to keep the diversity of individuals and overcome the problem of premature convergence. The proposed MOGA is evaluated on some representative instances and the comparison with other approaches in the latest papers validates the effectiveness of the proposed algorithm. Finally, the analytic hierarchy process (AHP) approach is used to select the satisfied solution.For the undetermined environment, fuzzy set is introduced to solve multi-objective FJSP with undetermined processing time and due date. Based on the improved MOGA proposed, we solved the multi-objective flexible job shop scheduling problem with fuzzy processing time and fuzzy due date. The computational results validate the effectiveness of the proposed algorithm.MOGA based on rolling-horizon procedure was proposed to solve the multi-objective dynamic FJSP. In this procedure, periodic and event driven rescheduling strategies were employed and the dynamic scheduling problem was decomposed into a series of continual and static scheduling problems, then the improved MOGA was applied to optimize each of the static scheduling problems. According to the characteristics of the dynamic scheduling problem, the efficient decoding procedure and genetic operators were presented for the improved multi-objective genetic algorithm, and the objectives of rescheduling were to minimize the makespan, total tardiness, the mean flow-time, deviations from the pre-schedule. In order to adapt to the complex manufact uring environment and sustain the stability of production, a human-computer collaborative scheduling procedure was presented for the implementation of the scheduling process. The approach was tested on the instance, and the simulation results validate the effectiveness of the proposed strategies.Real production workshop oriented scheduling prototype system is designed and developed based on the research findings above. The system architecture, development principles and function modules are described.Finally, the research in the whole dissertation is summarized and future work is generalized and looked forward.更多还原