【作者】 何伟；

【导师】 孙棣华；

【作者基本信息】 重庆大学 ， 控制理论与控制工程， 2012， 博士

【摘要】 车间调度问题是制造系统理论研究的基础问题之一，主要讨论在有限的制造资源条件下将工件合理地分配到各个制造资源，并在满足加工约束的前提下使得一个或多个目标达到最优。随着社会需求快速变化，产品生产周期不断缩短，制造业正向着多品种，小批量的方向发展，柔性已成为生产制造过程所追求的重要特性之一。柔性Job Shop调度问题(Flexible Job Shop Problem, FJSSP)由于具有加工路径柔性的特点，与传统的Job Shop相比更符合实际的生产环境和要求，因而成为车间调度的一个重要的研究方向。在实际生产环境中，往往存在许多不确定因素，机器故障就是常见的典型不确定因素，它不仅会导致实际生产结果和计划产生重大偏差，而且可能打乱诸如物料配送等相关生产环节，对生产过程带来重大影响。因此，研究机器故障下的柔性Job Shop调度对提高生产过程的管理和控制水平具有重要的理论和实际意义。对机器故障条件下的柔性Job Shop的调度，其目标是尽可能降低实际调度和调度计划的偏差，从而保证产品按时交付。鲁棒性和稳定性是评价机器故障下柔性Job Shop调度的两个重要指标，和控制理论中的鲁棒性和稳定性不同，它们分别反映了整体的实际调度结果和计划的偏差以及每个工序实际完成时间和计划完成时间的偏差。因此机器故障下的柔性Job Shop调度目标就是努力提高调度的鲁棒性和稳定性。本文针对机器故障这一典型不确定因素，以提高调度的鲁棒性和稳定性为研究目标来研究机器故障下柔性Job Shop调度问题。研究工作主要从两个方面展开：一是研究多种策略组合下的预调度和重调度方法，二是研究机器故障下重调度的博弈模型和策略。首先，针对单一策略下得到的调度策略在鲁棒性和稳定性方面的不足，将多种调度策略引入到预调度和重调度过程中。其次，从鲁棒性和稳定性之间的均衡出发，研究了基于静态和动态博弈理论的调度模型和调度算法以寻找Nash均衡解。再次，针对基于工序完成时间不能完全反映调度的稳定性，研究并提出新的稳定性指标。最后，针对3个或以上的优化目标，研究了基于Pareto机制的人工免疫算法寻找Nash均衡。具体的研究内容如下：（1）针对单一调度策略不能较好地保障机器故障下调度的鲁棒性和稳定性，提出了基于机器故障概率的预调度策略和右移及更改加工路径的混合重调度策略。首先假设在机器故障概率为已知的条件下，根据机器故障的概率在生成的预调度中插入适当数量的空闲时间。其次在机器发生故障时采用右移和变换加工路径调度策略，尽可能保证调度的鲁棒性和稳定性，最后给出了基于二叉树的右移调度算法和右移与变换加工路径相结合的调度算法。实验结果表明，和单一的右移策略以及完全重调度相比，本文所提出的策略能够得到较好的鲁棒性和稳定性。（2）考虑到鲁棒性和稳定性之间的均衡性存在博弈关系，建立了基于静态博弈的重调度模型，并给出寻找Nash均衡解的算法；考虑到可能存在多个Nash均衡和不存在Nash均衡情况，提出了寻找近似Nash均衡的方法；针对受影响工序超过2个的情况，提出多阶段博弈的调度算法。由于调度的鲁棒性和稳定性指标可以看成具有决策能力的实体，两者为保持各自的最优性能的决策过程可以看成是博弈的过程，因此运用静态博弈的相关理论与方法，建立了机器故障下重调度的静态博弈模型。由于博弈双方采用纯策略，针对可能出现无Nash均衡解或着多个Nash均衡解的情况，提出了寻找近似Nash均衡解的方法；对于受影响工序超过两个时策略空间的急剧膨胀的情况，提出了多阶段博弈的思想。实验结果表明，采用静态博弈模型能够提高调度的鲁棒性和稳定性。（3）从博弈过程中决策有先后顺序的角度出发，运用动态博弈理论，建立了机器故障下动态博弈的重调度模型，给出了求解子博弈完美Nash均衡的算法。在静态博弈的基础上进一步考虑博弈双方决策的先后顺序，建立基于动态博弈的重调度模型。为求解子博弈完美Nash均衡，给出基于博弈树的求解子博弈完美Nash均衡的算法。在生产过程后期发生机器故障时，采用该模型能够得到较好的鲁棒性和稳定性。（4）针对基于工件加工完成时间的稳定性指标的不足，提出了基于工序的加工机器分配的稳定性指标。基于工序完成时间的稳定性指标不能完全反映调度的稳定性，论文从资源分配的角度出发，在已有稳定性的基础上定义了基于工序的机器分配的稳定性指标，增加该指标能更加全面反映调度的稳定性。（5）针对两个以上的调度目标，上述寻找Nash均衡的方法不再适用，论文提出了将Nash均衡和Pareto最优相结合的改进的人工免疫克隆算法。机器故障下对重调度的鲁棒性和稳定性进行优化可归结为多目标优化问题。当调度目标多于两个时，本文将Nash均衡和Pareto机制引入到人工免疫克隆算法之中，并运用该算法寻找Nash均衡解。仿真结果表明，对于三个目标的调度问题，本文提出的方法能够寻找到较好的Nash均衡解。综上所述，本文以提高调度的鲁棒性和稳定性为目标，研究了对机器故障下的柔性Job Shop的预调度和重调度策略，然后从博弈的角度对该问题进行了研究，为求解机器故障下车间调度多目标优化问题提供了一种新的思路。更多还原

【Abstract】 Job Shop Scheduling Problem (JSP) is one of the hotspots in the fields ofmanufacturing. This problem considers how to allocate workpieces to the machines withresources limitation and make one or more objectives become optimal under theconstraints of the problem. With the variation of the demand of the society and the shortcycle of the production, manufacturing is progressing towards multi-type of productionand small batches. Flexibility becomes one of the most important features ofmanufacturing. Flexible Job Shop Scheduling has the feature of flexibility due to itsflexible processing routing. Compared with traditional Job Shop, it much better fit forthe reality and become an important area of manufacturing.In real manufacturing, there are many uncertainties and machine breakdown is oneof the typical uncertainties which not only brings deviation to the plan but also disturbssome production phase such as transportation of material. Hence, studying on FJSSPwith machine breakdown is important to improve the manufacturing management andcontrol level.The objective of FJSSP is to struggle to decrease the deviation of the realscheduling and the plan, so as to assure the delivery of production. Robustness andstability are the two important indexes which are employed to evaluate the schedulingof FJSSP with machine breakdown. Different from the concepts defined in controltheory, robustness and stability defined in the problem means the deviation of the resultsof real scheduling and the plan and the deviation of end time of each operation. Hence,the objective of FJSSP with machine breakdown is trying to improve the robustness andstability.This dissertation studies the approaches to improve the robustness and stability ofFJSSP with machine breakdown in two aspects: one is that it studies the approaches ofpre-scheduling and re-scheduling with multiple strategies; another is that it studies thescheduling model and strategies based on game theory. Firstly, the strategies ofpre-scheduling and re-scheduling are studied considering single strategy may not obtainbetter robustness and stability. Secondly, from the equilibrium of the two objects pointof view, the model and algorithms based on static and dynamic game theory are alsostudied. Thirdly, a new stable measure is proposed due to the existing stable measurebased on the time of each finished operation not fully reflect the stable feature of scheduling. Lastly, an artificial immune clone algorithm based on Pareto mechanism isresearched to find Nash equilibriums. The important researches are as follows:A new method with multiple strategies is proposed on account of single strategynot being able to guarantee the robustness and stability of scheduling with machinebreakdown. This new method inserts appropriate number of idle times into thepre-scheduling according to the probability of machine breakdown which is known inadvance. When machine breakdown happens, the strategy combined with right shift androute changing is applied to handle machine breakdown. The algorithm of right shiftbased on binary tree and the algorithm of strategy combined with right shift and routechanging are also presented. Experiments shows that compared with single right shiftand full re-scheduling, the strategies proposed in this dissertation can obtain betterrobust and stable capabilities.Considering equilibrium of robustness and stability has the game relationship, anew model based on game theory for the problem is built and the method to find Nashequilibriums is also proposed. At the same time, considering there may have more Nashequilibriums or there has no Nash equilibrium, the algorithm to find near Nashequilibrium based on new concept called near Nash equilibrium is proposed.The robustness and stability can be taken as two entities which have the ability ofdecision-making, and robustness and stability can not reach to be best simultaneously inmost circumstances, the decision-making process of the entities who try to keep theperformance to be best can be seen as a game procedure. Hence, the game theory isapplied to build re-scheduling model based on static game for FJSSP under machinebreakdown. Because the two sides who take part in the game take pure strategies, theapproaches to find near NE and the algorithm for multi-stage game are proposedExperiments shows that the model and the algorithm can obtain better robust and stablecapabilities.Considering the sequence of the decision-making of the game procedure, a modelfor FJSSP with machine breakdown based on dynamic game theory was built and analgorithm for finding sub-game perfect Nash equilibrium was also proposed.Experiment shows that in the later stage of scheduling, this model can get better results.Due to the shortage of the stability performance based on the end time of eachoperation, a new stability index based on the machine allocation for each operation isput forward.The stability based on the end time of each operation can not fully reflect the stability of the whole scheduling, so a new stable measure based on machine allocationis proposed from the resource allocation point of view, it can fully reflect the stability ofthe scheduling.Because the approach to find NE with two objectives do not fit for the problemwith three or more objectives, an improved artificial immune clone algorithmintegrating Nash solution and Pareto mechanism is put up.The optimization for robustness and stability of the rescheduling under machinebreakdown can be considered as multi-objective problems. For the problems of three ormore objectives to be optimized, a Pareto optimization was introduced and improvedartificial immune clone algorithm was proposed to find Nash equilibrium solutions. Theresults of experiments reveal that this new method can find better Nash equilibriumsolutions. Simulation experiments reveal that the approach can find better NE in theoptimization of the problem having more than two objectives.To sum up, this dissertation takes the robust and stable measure as objectives, andthe strategies of pre-scheduling and rescheduling are studied. Then the problem is alsoresearched from game theory point of view. These works provide a new idea to solveFJSSP with machine breakdown.更多还原