【作者】 刘琳；

【导师】 席裕庚；

【作者基本信息】 上海交通大学 ， 控制理论与控制工程， 2007， 博士

【摘要】 生产调度的目的是在有限时域内为生产任务分配有限的车间资源来优化一个或者多个性能指标。以往的关于调度的研究主要集中在理想的调度环境,一般都是以确定性的数学模型为基础,与实际的车间调度环境存在很大差别。在实际的制造车间中,往往存在着很多动态不确定因素,如加工时间变动、机器故障或者交货期变更等。如何在生成预调度时考虑到不确定因素的影响,已经成为解决实际问题的关键。不确定因素可以分为部分已知和完全未知两类,对于第一类情况,在建立预调度优化模型时,就应考虑这些因素的影响,可以有效提高调度的鲁棒性和稳定性;而对于第二类情况,采用反应式的重调度是适应环境变化的最好解决方式。在动态不确定环境下的调度问题,其计算复杂度远远超过了静态调度问题,使得以往的研究方法难以直接应用,对问题的求解提出了更高的要求。本文围绕着动态不确定环境下的调度问题展开研究,主要研究了三种典型的情况:加工时间不确定、机器随机故障和工件到达时间未知。本文的主要工作包括如下五个方面:1.首先研究了加工时间不确定的单机Just-In-time调度问题。因为在加工时间确定时,不存在一个多项式时间算法得到问题的最优调度,所以采用了绝对鲁棒指标以最小化所有可能加工时间下的最大代价,这是一个minimax优化问题。在给定调度顺序后,内层max优化问题的决策空间是加工时间构成的凸多面体,而优化目标是关于加工时间的凸函数,则可以在凸多面体的顶点取得max问题的极值,因此大大降低了问题的搜索空间。根据minimax问题特性设计了一种两层遗传算法,与以期望时间为基础的确定性调度算法相比,在多种加工时间情况下设计的算法得到了更加鲁棒的调度。2.将对不确定加工时间情况下的鲁棒调度问题的研究从单机扩展到Job Shop。相对于单机问题,Job Shop中的约束更加复杂,增加了同一工件所有工序的先后顺序约束,因此不具有类似于单机内层max问题的特性,其搜索空间为整个加工时间的可行域,大大增加了计算复杂度。相对于解决单机问题的两层算法,从兼顾算法性能和计算效率的角度出发,设计了一种双空间协同进化遗传算法,仿真测试表明了算法的有效性。3.研究了机器随机故障情况下兼顾稳定性的单机鲁棒调度问题,该问题是一个双目标优化问题。在调度执行之前,无法获得真实的性能指标,因此采用期望指标。通过将多次故障集结为一次故障,并采用右移重调度处理故障,简化了对调度的鲁棒性和稳定性指标的估算。采用权重和方法将双目标转化为单目标问题,设计了两阶段多种群遗传算法有效确定双目标优化问题的Pareto最优解。在仿真试验中,对四种不同方法进行了对比分析,同时比较了随机权重和固定权重情况下算法的性能,结果表明了随机权重比固定权重具有更好的搜索能力。4.将单机的研究成果扩展到机器随机故障情况下兼顾稳定性的Job Shop鲁棒调度问题。与单机问题求解算法的不同之处在于染色体的编码方式,不仅包含了表达工序优先关系的基因,还包含了计算插入空闲时间大小的基因。由于Job Shop自身约束的复杂性,对调度的鲁棒性和稳定性指标计算更加困难,因此采用了采样方法进行估算。在仿真试验中,对未考虑空闲时间影响和考虑空闲时间影响的两种算法进行了对比分析,结果表明了后者比前者较大程度改善了稳定性,对鲁棒性的影响程度很小。5.对工件到达时间未知的动态Job Shop滚动重调度问题进行了深入研究,提出了关键工序集的概念。在滚动时域分解方法框架下,以时间窗口作为滚动窗口,设计了基于关键工序集的滚动重调度算法。采用混和遗传算法有效地确定关键工序集及其最优调度顺序,对关键工序集之外的工序,采用了分派规则确定在机器上的加工顺序,最后以完全调度的目标值评价染色体的适应度。与基于完全工序集的算法相比,大大降低了搜索空间。仿真试验表明,基于关键工序集的算法极大提高了计算效率,对全局性能指标的影响程度很小,为实际生产中的大规模动态调度问题提供了一种新思路。更多还原

【Abstract】 Production scheduling is a combinatorial optimization problem, which concerns the allocations of limited resources such as machines, material and tools to competing tasks in order to optimize one or more objectives. Previous work mostly focused on deterministic scheduling problems with an assumption that the manufacturing environment is ideal,thus there is a large gap between theory and practice of production scheduling. There are many kinds of uncertainties in the practical manufacturing system, such as variant processing times, machine breakdowns and due date changes. Considering the influence of uncertainties when generating the predictive schedule is the key problem to bridge the gap between theory and practice. The uncertainties are generally classified two categories: partial known and complete unknown. For the partial known uncertainties, it is necessary to consider the influence of these uncertainties in the optimization model to improve the robustness and stability of the schedule. For the complete unknown uncertainties, rescheduling is the best method. In the dynamic and uncertain environments, scheduling becomes more complicate than the static one, which brings many difficulties to directly use the methods for the static problem. In this thesis, our research is focused on three classic uncertainties including uncertain job processing times, random machine breakdowns and unknown job arriving times.The main research work lies in five aspects as follows.1. The research focuses on absolute robust scheduling for a single machine to minimize total weighted earliness and tardiness with uncertain job processing times. There is no polynomial algorithm to find the optimal schedule with deterministic job processing times. Thus the absolute robust performance is used find a schedule with the best worst-case performance over all potential realizations of job processing times. It is inherently a minimax optimization problem. For a given schedule sequence, the decision space of the max problem is the convex polyhedron composed of job processing times. Since the objective is a convex function respect to job processing times, the maximum is lies at a vertex of the convex polyhedron, which significantly reduces the search space of inner loop. A two loop genetic algorithm is designed to solve the minimax problem and the algorithm generates more robust schedule than the deterministic algorithm with expected processing times.2. The job shop scheduling with uncertain processing times is studied. Compared with the single machine scheduling, there are sequence constraints of a same job in addition to machine capacity constraints in a job shop. Thus the job shop absolute scheduling has not the same property of the inner max optimization as the single machine absolute scheduling. The search space of the inner max problem is the whole feasible region. The designed genetic algorithm with two evolving populations to improve the computational efficiency compared with the algorithm for single machine. The simulation results on many random instances show the algorithm is effective.3. The single machine scheduling problem with random machine breakdowns is firstly described. The scheduling considering both robustness and stability is a bi-objective optimization. Since the robustness and stability are unavailable before completing the schedule, the computation of both two objectives is very important. Surrogate measures are designed to evaluate both robustness and stability by aggregating all possible breakdowns into one breakdown. The weighted linear method is used to convert the bi-objective into a single objective. A two-stage multi-population genetic algorithm is proposed to generate Pareto optimal solution effectively. The simulation experiments are taken on many instances using four different methods. Also, the performance of the algorithm is analyzed when the linear weight is a random value and a constant one.4. For the complex job shop with random machine breakdowns, the chromosome of the proposed two-stage multi-population genetic algorithm includes not only genes representing priorities of all operations but also genes computing the amount of additional inserted idle times. The sampling method is used to evaluate robustness and stability. In computational experiments, the algorithm with considering effects of idle times on the schedule and the one without are compared. The results show that the former improves the stability obviously with a little degradation of robustness.5. Based on the framework of rolling horizon decomposition, the critical operation set is defined for the dynamic job shop scheduling with uncertain arrival times. The rolling window is time-based and the hybrid genetic algorithm is proposed to determine the sequence of the critical operation set as well as optimizing the global objective. A dispatching rule is used to determine the sequence of the operations out of the critical operation set. The fitness of a chromosome is measured by the complete schedule for the total available operations at the current rescheduling time. The simulation results of many instances show the proposed algorithm significantly improves the computational efficiency with sacrificing the schedule performance in a bit degree compared with the genetic algorithm for the complete operation set. Thus, the critical set definition is a useful idea for large-scale production scheduling systems.更多还原