动态不确定环境下生产调度算法研究
|
摘要
生产调度的目的是在有限时域内为生产任务分配有限的车间资源来优化一个或者多个性能指标。以往的关于调度的研究主要集中在理想的调度环境,一般都是以确定性的数学模型为基础,与实际的车间调度环境存在很大差别。在实际的制造车间中,往往存在着很多动态不确定因素,如加工时间变动、机器故障或者交货期变更等。如何在生成预调度时考虑到不确定因素的影响,已经成为解决实际问题的关键。不确定因素可以分为部分已知和完全未知两类,对于第一类情况,在建立预调度优化模型时,就应考虑这些因素的影响,可以有效提高调度的鲁棒性和稳定性;而对于第二类情况,采用反应式的重调度是适应环境变化的最好解决方式。在动态不确定环境下的调度问题,其计算复杂度远远超过了静态调度问题,使得以往的研究方法难以直接应用,对问题的求解提出了更高的要求。本文围绕着动态不确定环境下的调度问题展开研究,主要研究了三种典型的情况:加工时间不确定、机器随机故障和工件到达时间未知。
本文的主要工作包括如下五个方面:
1.首先研究了加工时间不确定的单机Just-In-time调度问题。因为在加工时间确定时,不存在一个多项式时间算法得到问题的最优调度,所以采用了绝对鲁棒指标以最小化所有可能加工时间下的最大代价,这是一个minimax优化问题。在给定调度顺序后,内层max优化问题的决策空间是加工时间构成的凸多面体,而优化目标是关于加工时间的凸函数,则可以在凸多面体的顶点取得max问题的极值,因此大大降低了问题的搜索空间。根据minimax问题特性设计了一种两层遗传算法,与以期望时间为基础的确定性调度算法相比,在多种加工时间情况下设计的算法得到了更加鲁棒的调度。
2.将对不确定加工时间情况下的鲁棒调度问题的研究从单机扩展到Job Shop。相对于单机问题,Job Shop中的约束更加复杂,增加了同一工件所有工序的先后顺序约束,因此不具有类似于单机内层max问题的特性,其搜索空间为整个加工时间的可行域,大大增加了计算复杂度。相对于解决单机问题的两层算法,从兼顾算法性能和计算效率的角度出发,设计了一种双空间协同进化遗传算法,仿真测试表明了算法的有效性。
3.研究了机器随机故障情况下兼顾稳定性的单机鲁棒调度问题,该问题是一个双目标优化问题。在调度执行之前,无法获得真实的性能指标,因此采用期望指标。通过将多次故障集结为一次故障,并采用右移重调度处理故障,简化了对调度的鲁棒性和稳定性指标的估算。采用权重和方法将双目标转化为单目标问题,设计了两阶段多种群遗传算法有效确定双目标优化问题的Pareto最优解。在仿真试验中,对四种不同方法进行了对比分析,同时比较了随机权重和固定权重情况下算法的性能,结果表明了随机权重比固定权重具有更好的搜索能力。
4.将单机的研究成果扩展到机器随机故障情况下兼顾稳定性的Job Shop鲁棒调度问题。与单机问题求解算法的不同之处在于染色体的编码方式,不仅包含了表达工序优先关系的基因,还包含了计算插入空闲时间大小的基因。由于Job Shop自身约束的复杂性,对调度的鲁棒性和稳定性指标计算更加困难,因此采用了采样方法进行估算。在仿真试验中,对未考虑空闲时间影响和考虑空闲时间影响的两种算法进行了对比分析,结果表明了后者比前者较大程度改善了稳定性,对鲁棒性的影响程度很小。
5.对工件到达时间未知的动态Job Shop滚动重调度问题进行了深入研究,提出了关键工序集的概念。在滚动时域分解方法框架下,以时间窗口作为滚动窗口,设计了基于关键工序集的滚动重调度算法。采用混和遗传算法有效地确定关键工序集及其最优调度顺序,对关键工序集之外的工序,采用了分派规则确定在机器上的加工顺序,最后以完全调度的目标值评价染色体的适应度。与基于完全工序集的算法相比,大大降低了搜索空间。仿真试验表明,基于关键工序集的算法极大提高了计算效率,对全局性能指标的影响程度很小,为实际生产中的大规模动态调度问题提供了一种新思路。
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.
本文的主要工作包括如下五个方面:
1.首先研究了加工时间不确定的单机Just-In-time调度问题。因为在加工时间确定时,不存在一个多项式时间算法得到问题的最优调度,所以采用了绝对鲁棒指标以最小化所有可能加工时间下的最大代价,这是一个minimax优化问题。在给定调度顺序后,内层max优化问题的决策空间是加工时间构成的凸多面体,而优化目标是关于加工时间的凸函数,则可以在凸多面体的顶点取得max问题的极值,因此大大降低了问题的搜索空间。根据minimax问题特性设计了一种两层遗传算法,与以期望时间为基础的确定性调度算法相比,在多种加工时间情况下设计的算法得到了更加鲁棒的调度。
2.将对不确定加工时间情况下的鲁棒调度问题的研究从单机扩展到Job Shop。相对于单机问题,Job Shop中的约束更加复杂,增加了同一工件所有工序的先后顺序约束,因此不具有类似于单机内层max问题的特性,其搜索空间为整个加工时间的可行域,大大增加了计算复杂度。相对于解决单机问题的两层算法,从兼顾算法性能和计算效率的角度出发,设计了一种双空间协同进化遗传算法,仿真测试表明了算法的有效性。
3.研究了机器随机故障情况下兼顾稳定性的单机鲁棒调度问题,该问题是一个双目标优化问题。在调度执行之前,无法获得真实的性能指标,因此采用期望指标。通过将多次故障集结为一次故障,并采用右移重调度处理故障,简化了对调度的鲁棒性和稳定性指标的估算。采用权重和方法将双目标转化为单目标问题,设计了两阶段多种群遗传算法有效确定双目标优化问题的Pareto最优解。在仿真试验中,对四种不同方法进行了对比分析,同时比较了随机权重和固定权重情况下算法的性能,结果表明了随机权重比固定权重具有更好的搜索能力。
4.将单机的研究成果扩展到机器随机故障情况下兼顾稳定性的Job Shop鲁棒调度问题。与单机问题求解算法的不同之处在于染色体的编码方式,不仅包含了表达工序优先关系的基因,还包含了计算插入空闲时间大小的基因。由于Job Shop自身约束的复杂性,对调度的鲁棒性和稳定性指标计算更加困难,因此采用了采样方法进行估算。在仿真试验中,对未考虑空闲时间影响和考虑空闲时间影响的两种算法进行了对比分析,结果表明了后者比前者较大程度改善了稳定性,对鲁棒性的影响程度很小。
5.对工件到达时间未知的动态Job Shop滚动重调度问题进行了深入研究,提出了关键工序集的概念。在滚动时域分解方法框架下,以时间窗口作为滚动窗口,设计了基于关键工序集的滚动重调度算法。采用混和遗传算法有效地确定关键工序集及其最优调度顺序,对关键工序集之外的工序,采用了分派规则确定在机器上的加工顺序,最后以完全调度的目标值评价染色体的适应度。与基于完全工序集的算法相比,大大降低了搜索空间。仿真试验表明,基于关键工序集的算法极大提高了计算效率,对全局性能指标的影响程度很小,为实际生产中的大规模动态调度问题提供了一种新思路。
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.
引文
[1] Panwalkar S.S. and Iskander W. A survey of scheduling rules. Operations Research, 1997, 25(1): 45-61
[2] Green G.I. and Appel L.B. An empirical analysis of job shop dispatch rule selection. Journal of Operations Management, 1981, 1(4): 197-203
[3] Hopp W.J. and Spearman M.L. Factory physics. Irwin/McGraw-Hill, Boston, 1996
[4] 王长军. 基于非合作博弈的生产调度建模与算法研究. 上海交通大学博士学位论文, 2006
[5] 唐国春, 张峰, 罗守成, 刘丽丽著. 现代排序论. 上海: 上海科学普及出版社, 2003
[6] Natalia V.S., Yuri N.S.and Frank W. Complexity of mixed shop scheduling problems: a survey. European Journal of Operational Research, 2000, 120(2): 343-351
[7] Jain A.S. and Meeran S. Deterministic Job shop scheduling: past, present and future. European Journal of Operational Research, 1999, 113(2): 390-434
[8] Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. and Shmoys D.B. Sequencing and scheduling: algorithms and complexity. In: Handbook in Operations Research and Management Science 4: Logistics of Production and Inventory, 1993
[9] Geoff L. Application of mathematical programming—before, now and after. Operation Research Society, 1985, 35(5): 347-356
[10] Taha H.A. Integer programming. New York: Academic Press, 1975
[11] Bellman R. Esogbue A.O. and Nabeshima I. Mathematical aspects of scheduling and application. Pergamon Press, New York, 1982
[12] Bellman R. Dynamic programming. Princeton University Press, USA, 1957
[13] Held M. and Karp R.M. A dynamic programming approach to sequencing problems. Journal of SIAM. 1962, 10(1): 196-210
[14] Carlier J. and Pinson E. An algorithm for solving the job-shop problem. Management Science, 1989, 35(2): 164-176
[15] Belouadah H., Posner M.E. and Potts C.N. Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Applied Mathematics, 1992, 36(3): 213-231
[16] Maccarthy B.L. and Liu J. Addressing the gap in scheduling research: a review of optimization and heuristic method in production scheduling. International Journal of Production Research, 1993, 31(1): 59-79
[17] Johnson S.M. Optimal two- and three-stage production schedules with set-up times. Naval Research Logistics Quarterly, 1954, 1: 61-68
[18] Blackstone J.H., Philips D.T. and Hogg G.T. A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 1982, 20(1): 27-46
[19] Kirkpatrick S., Gelatt C.D. and Vecchi M.P. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680
[20] Laarhoven P.J.M.V., Aarts E.H.L. and Lenstra J.K. Job shop scheduling by simulated annealing. Operations Research, 1992, 40(1): 113-125
[21] Satake T., Morikawa K., Takahashi K. and Nakamura N. Simulated annealing approach forminimizing the makespan of the general job-shop. International Journal of Production Economics, 1999, 60-61: 515-522
[22] Glover F. Tabu search - Part I. ORSA Journal on computing, 1989, 1(3): 190-206
[23] Glover F. Tabu search - Part II. ORSA Journal on computing, 1990, 2(1): 4-32
[24] Taillard E.D. Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 1994, 6(2): 108-117
[25] Nowicki E. and Smutnicki C. A fast taboo search algorithm for the job shop problem. Management Science, 1996, 42(2): 797-813
[26] Davis L. Job-shop scheduling with genetic algorithm. Proceedings of International Conference on Genetic Algorithm and their Application. 1985
[27] Groce F.D., Tadei R. and Volta G. A genetic algorithm for the job shop problem. Computers and Operations Research, 1995, 22(1): 15-24
[28] Binato S., Hery W.J., Loewenstern D.M. and Resende M.G.C. A GRASP for job shop scheduling. In: Ribeiro, C.C., Hansen, P. (Eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2002
[29] Mattfeld D.C. and Bierwirth C. An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research. 2004, 155(2): 616–630
[30] 王凌, 郑大钟.求解同顺序加工调度问题的一种改进遗传算法. 系统工程理论与实践, 2002, 22(6): 74-79
[31] 李岩, 吴智铭. 基于约束逻辑规划和遗传算法的柔性调度. 控制与决策, 2002, 17(3): 297-300
[32] 杨红红. 遗传算法在制造系统计划与调度优化中的应用. 上海交通大学博士学位论文, 2002
[33] 顾幸生, 郑璐, 李平, 张伟. 不确定性条件下存储时间有限型 Flow Shop 问题的提前/拖期调度研究. 华东理工大学学报, 2004, 30(3: 322-327
[34] Fonseca C.M. and Fleming P.J. An overview of evolutionary algorithm in multi-objective optimization. Evolutionary Computation, 1995, 3(1): 1-16
[35] Tamaki H., Kita H. and Kobayashi S. Multiobjective optimization by genetic algorithm: a review. In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 1996: 517–522
[36] Horn J. Multicriterion decision making. The Handbook of Evolutionary Computation. Oxford University Press, New York, 1997, F1.9: 1-15
[37] Kiran A.S. and Smith M.L. Simulation studies in Job shop scheduling-I a survey. Computer and Industry Enginieering, 1984, 8(2): 87-93
[38] Wu S.Y.D. and Richard A.W. An application of discrete-event simulation to on-line control and scheduling in flexible manufacturing. International Journal of Production Research, 1989, 27(9): 1603-1623
[39] Ovacik I.M. and Uzsoy R. Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times. International Journal of Production Research, 1994, 32(6): 1243-1263
[40] Ovacik I.M. and Uzsoy R., Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times. International Journal of Production Research, 1995, 33(11): 3173-3192
[41] Ovacik I.M. and Uzsoy R. Decomposition methods for complex factory scheduling problems. Boston/Dordrecht/London: Kluwer Academic Publishers, 1997
[42] Luh P.B. and Hoitomt D.J. Scheduling of manufacturing systems using the lagrangian relaxation technique. IEEE Transactions on Automatic Control, 1993, 38(7): 1066-1079
[43] Adams J., Balas E. and Zawack D. The shifting bottleneck procedure for job shop scheduling. Management Science, 1988, 34(3): 391-401
[44] Wang J. and Luh P.B. A combined Lagrangean relaxation relation and dynamic programming algorithm for job shop scheduling. In Proceedings 5th International Conference on Computer Integrated Manufacturing Automatic Technology, Grenoble, France, May 1996: 3-8
[45] Chen D., Liu F. and Luh P. B. Scheduling job shops with uncertainties. Proceedings of the 36th Conference on Decision and Control, San Diego, California USA, 1997
[46] 席裕庚. 预测控制. 国防工业出版社, 1993
[47] 席裕庚. 动态不确定环境下广义控制问题的预测控制. 控制理论与应用, 2000, 17(5): 665-670
[48] Fang J. and Xi Y.G. A rolling horizon job shop rescheduling strategy in the dynamic environment. The International Journal of Advanced Manufacturing Technology. 1997, 13(3): 227-232
[49] 方剑, 席裕庚. 基于遗传算法的滚动调度策略. 控制理论与应用. 1997, 14(4): 589-594
[50] 王冰. 滚动时域调度方法及其性能分析研究. 上海交通大学博士学位论文, 2005
[51] Carlier J. The one-machine sequencing problem. European Journal of Operational Research, 1982, 11(1): 42-47
[52] Dauzere-Peres S. and Lasserre J. A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research 1993, 31(4): 923-932
[53] Applegate D. and Cook W. A computational study of the job shop scheduling problem. ORSA Journal of Computing, 1991, 3(2): 149-156
[54] Balas E., Lenstra J. and Vazacopoulos A. The one-machine problem with delayed precedence constraints and its use in the job shop scheduling. Management Science 1995, 41(1): 94-109
[55] Ramudhin A. and Philip M. The generalized shifting bottleneck procedure. European Journal of Operational Research. 1996, 93(1): 34-48
[56] Pinedo M. and Singer M. A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research and Logistics 1999, 46: 1-17
[57] Singer M. Decomposition methods for large job shops. Computers and Operations Research 2001, 28(3): 193-207
[58] Suresh V. and Chandhuri D. Dynamic scheduling-A survey of research. International Journal of Production Economics, 1993, 32(1): 53-63
[59] Vieira G.E., Herrmann J.W. and Lin E. Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1): 39-62
[60] Pinedo M. Scheduling: theory, algorithms and systems. Prentice-Hall, Englewood Cliffs, 1995
[61] Church L.K. and Uzsoy R. Analysis of periodic and event-driven rescheduling policies in dynamic shops. International Journal of Computer Integrated Manufacturing, 1992, 5(3): 153-163
[62] Kamoun H. and Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacturing systems. European Journal of Operational Research, 1993, 70(3): 350-364
[63] Hall N.G. and Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 1996, 44(3): 510-525
[64] Markowitz, D.M. and Lawrence M.W. Heavy traffic analysis of dynamic cyclic policies: a unified treatment of the single machine scheduling problem. Operations Research, 2001, 49(2): 246-270
[65] Abumaizar R.J. and Svestka J.A. Rescheduling job shops under disruptions. International Journal ofProduction Research, 1997, 35(7): 2065-2082
[66] Yamamoto M. and Nof S.Y. Scheduling/rescheduling in the manufacturing operating system environment. International Journal of Production Research, 1985, 23(4): 705-722
[67] Wu S.D., Storer R.H. and Chang P.C. One-machine rescheduling heuristics with efficiency and stability as criteria. Computers and Operations Research, 1993, 20(1): 1-14
[68] Cowling P.I. and Johansson M. Using real time information for effective dynamic scheduling, European Journal of Operational Research, 2002, 139(2): 230-244
[69] Sabuncuoglu I. and Karabuk S. Rescheduling frequency in an FMS with uncertain processing times and unreliable machines. Journal of Manufacturing Systems, 1999, 18(4): 268-283
[70] Vollmann T.E., Berry W.L. and Whybark D.C. Manufacturing planning and control systems, fourth edition, Irwin/McGraw-Hill, New York, 1997
[71] Jain A.K. and Elmaraghy H.A. Production scheduling/rescheduling in flexible manufacturing. International Journal of Production Research, 1997, 35(1): 281-309
[72] Henning G.P. and Cerda J. An expert system for predictive and reactive scheduling of multiproduct batch plants. Latin American Applied Research, 1995, 25: 187-198
[73] Vieira G.E., Herrmann J.W. and Lin E. Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies. International Journal of Production Research, 2000, 38(8): 1899-1915
[74] Vieira G.E., Herrmann J.W. and Lin E. Predicting the performance of rescheduling strategies for parallel machine systems. Journal of Manufacturing Systems, 2000, 19(4): 256-266
[75] Shafaei R. and Brunn P. Workshop scheduling using practical (inaccurate) data - Part 2: An investigation of the robustness of scheduling rules in a dynamic and stochastic environment. International Journal of Production Research, 1999, 37(18), 4105-4117
[76] Kempf K.G. Intelligently scheduling semiconductor wafer fabrication. Intelligent Scheduling, Zweben M. and Fox M.S. ed., Morgan Kaufmann Publishers, San Francisco, 1994
[77] Smith S. Reactive scheduling systems. Intelligent scheduling systems, Brown D.E. and Scherer W.T., ed., Kluwer Press, 1995
[78] Monostori L., Szelke E. and Kadar B. Management of changes and disturbances in manufacturing systems. Annual Reviews in Control, Pergamon Press, Elsevier Science, 1998, 22: 85-97
[79] Sabuncuoglu I. and Bayiz M. Analysis of reactive scheduling problems in a Job shop environment. European Journal of Operational Research, 2000, 126(3): 567-586
[80] Sun J. and Xue D. A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources. Computers in Industry, 2001, 46(2): 189-207
[81] Perkins J.R. and Kumar P.R. Stable distributed, real-time scheduling of flexible manufacturing/assembly/disassembly systems. IEEE Transactions on Automatic Control, 1989, 34(2): 139-148
[82] Chase C. and Ramadge P.J. On real-time scheduling policies for flexible manufacturing systems. IEEE Transactions on Automatic Control, 1992, 37(4): 491-496
[83] Huang Y.G., Kanal L.N. and Tripathi S.K. Reactive scheduling for a single machine: Problem definition, analysis, and heuristic solution. International Journal of Computer Integrated Manufacturing, 1990, 3(1): 6-12
[84] Szelke E. and Kerr R. Knowledge-based reactive scheduling. Production Planning & Control, 1994, 5(2): 124-145
[85] Herrmann J.W., Lee C.Y. and Hinchman J. Global job shop scheduling with a genetic algorithm.Production and Operations Management, 1995, 4(1): 30-45
[86] Li R.-K., Shyu Y.-T. and Adiga S. A heuristic rescheduling algorithm for computer-based production scheduling systems. International Journal of Production Research, 1993, 31(1): 1815-1826
[87] Kim M.H. and Kim Y.-D. Simulation-based real-time scheduling in a flexible manufacturing system. Journal of Manufacturing Systems, 1994, 13(2): 85-93
[88] Bierwirth C. and Mattfeld D.C. Production scheduling and rescheduling with genetic algorithms. Evolutionary Computation, 1999, 7(1): 1-17
[89] Wu H.-H., and Li. R.-K. A new rescheduling method for computer based scheduling systems. International Journal of Production Research, 1995, 33(8): 2097-2110
[90] Bean J.C., Birge J.R., Mittenthal J. and Noon C.E. Match up scheduling with multiple resources, release dates, and disruptions. Operation Research, 1991, 39(3): 470-483
[91] Selim A.M. and Gorgulu E. Match-up scheduling under a machine breakdown. European Journal of Operational Research, 1999, 112(1): 81-97
[92] Leon V.J., Wu S.D. and Storer R.H. Robustness measures and robust scheduling for job shops. IIE Transactions, 1994, 26(5): 32-43
[93] Mehta S.V. and Uzsoy R. Predictable scheduling of a job shop subject to breakdowns. IEEE Transactions on Robotics and Automation, 1998, 14(3): 365-378
[94] Mehta S.V. and Uzsoy R. Predictable scheduling of a single machine subject to breakdowns. International Journal of Computer Integrated Manufacturing, 1999, 12(1): 15-38
[95] O’Donovan R., Uzsoy R. and McKay K.N. Predictable scheduling of a single machine with breakdowns and sensitive jobs. International Journal of Production Research, 1999, 37(18): 4217-4233
[96] Byeon E.S., Wu S.D. and Storer R.H. Decomposition heuristics for robust job shop scheduling. IEEE Trans on Robotics and Automation, 1998, 14(2): 303-313
[97] Wu S.D., Byeon E.S. and Storer R.H. A Graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Operations Research, 1999, 47(1): 113-124
[98] Kouvelis P. and Yu G. Robust discrete optimization and its applications. Kluwer Academic Publishers, 1997
[99] Daniels R.L. and Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41(2): 363-376
[100] Kouvelis P., Daniels R.L. and Vairaktarakis G. Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Transactions, 2000, 32(5): 421-432
[101] Yang J. and Yu G. On the robust single machine scheduling problem. Journal of Combinatorial Optimization, 2002, 6(1): 17-33
[102] 李建更. 关于最优调度鲁棒性的研究. 南开大学博士学位论文, 2000
[103] 李建更, 涂菶生. 某些调度问题区间摄动鲁棒性研究. 自动化学报, 2001, 27(1): 24-30
[104] 李建更, 涂菶生. 一类 Flow shop 调度问题最优调度区间摄动鲁棒性. 控制理论与应用, 2004, 21(1): 25-29
[105] Herrmann J. W. A genetic algorithm for minimax optimization problems. In Angeline P. J. et al., editor, Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, 1999, 2: 1099-1103
[106] Jensen M.T. Finding worst-case flexible schedules using coevolution. In: Proc. of the Genetic and Evolutionary Computation Conference. Spector, L.et al. (Ed.). GECCO 2001, July 7-11, San Francisco, USA: 2001: 1144-1151
[107] Pinedo M. Stochastic scheduling with release dates and due dates. Operations Research, 1983, 31(3): 559-572
[108] Kanet J.J. Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly, 1981, 28: 643-651
[109] Hall N.G. and Posner M.E. Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Operations Research, 1991, 39(5): 836-846
[110] Hall N.G., Kubiak W. and Sethi S.P. Earliness-tardiness scheduling problems, II: deviation of completion times about a restrictive common due date. Operations Research, 1991, 39(5): 847-856
[111] Baker K.R. and Scudder G.D. Sequencing with earliness and tardiness penalties: a review. Operations Research, 1990, 38(1): 22-36
[112] Ow P.S. and Morton T.E. The single machine early/tardy problem. Management Science, 1989, 35(2): 177-191
[113] Sivrikaya-Serifoglu F. and Ulusoy G. Parallel machine scheduling with earliness and tardiness penalties. Computers and Operations Research, 1999, 26(8): 773-787
[114] 玄光男, 程润伟著. 遗传算法与工程设计. 科学出版社, 2000
[115] 玄光男, 程润伟著. 于歆杰 周根贵译. 遗传算法与工程优化. 清华大学出版社, 2004
[116] Lenstra J., Rinnooy K.A and Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1:343-362
[117] Holland J.H. Adaptation in natural and artificial Systems: An introductory analysis with applications to biology, control and artificial intelligence. 2nd ed. MIT Press, Cambridge, Massachusetts, 1992
[118] Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley, 1989
[119] Michalewicz Z. Genetic algorithm + Data structure = Evolution programs. Second Edition, Springer-Verlag, 1994
[120] Cheng R., Gen M. and Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers and Industrial Engineering, 1996, 36(2): 343-364
[121] Falkenauer E. and Bouffoix S. A genetic algorithm for job shop. In: Proceedings of the 1991 IEEE International Conference on Robotics and Automation, 1991: 824-849
[122] B?ck T. Selective, pressure in evolutionary algorithms: A characterization of selection mechanisms. In Proceedings of the first IEEE Conference on Evolutionary Computation, IEEE Press, 1994, 1: 57-62
[123] Grefenstette J.J. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics. 1986, 16(1): 122-128
[124] Mikkel T. Jensen. Robust and flexible scheduling with evolutionary computation. PhD Dissertation, Department of Computer Science University of Aarhus Denmark, 2001
[125] 王凌. 车间调度及遗传算法. 清华大学出版社, 2003
[126] Gen M., Tsujimura Y. and Kubota E. Solving job-shop scheduling problem using genetic algorithms. In proceedings of the 16th International Conference on Computer and Industrial Engineering, Ashikaga, Japan, 1994: 576-579
[127] Holsapple C., Jacob V., Pakath R. and Zaveri J. A genetic-based hybrid scheduler for generated static schedules in flexible manufacturing contexts. IEEE Trans On Systems, Man, and Cybernetics, 1993, 23(4): 953-971
[128] Davis L. Job shop scheduling with genetic algorithm. In Proceedings of the First InternationalConference on Genetic Algorithms (Edited by Grefenstette). Lawrence Erlbaum Associates, Hillsdale, NJ, 1985: 136-140
[129] Nakano R. and Yamada T. Conventional genetic algorithms for job-shop problems. In Proceedings of the Fourth International Conference on Genetic Algorithms (Edited by Belew and Booker). Morgan Kaufman, San Mateo, Calif, 1991: 477-479
[130] Dorndorf U. and Pesch E. Evolution based learning in a job shop scheduling environment. Computers and Operations Research, 1995, 22(1): 25-40
[131] Tamaki H. and Nishikawa Y. A paralleled genetic algorithm based on a neighborhood model and its application to the job shop scheduling. In Proceedings of the Second International Conference on Parallel Problem Solving from Nature, Elsevier Science Publishers North-Holland, 1992: 573-582
[132] Yamada T. and Nakano R. A genetic algorithm applicable to large-scale job-shop problems. In Proceedings of the Second International Conference on Parallel Problem Solving from Nature, Elsevier Science Publishers North-Holland, 1992: 281-290
[133] Bean J.C. Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on Computing, 1994, 6(2): 154-160
[134] Riezebos J. and Gaalman G.J.C. Time lag size in multiple operations flow shop scheduling heuristics, European Journal of Operational Research. 1998, 105(1): 72-90
[135] Fleszar Krzysztof and Hindi Khalil S. Solving the resource-constrained project scheduling problem by a variable neighbourhood search. European Journal of Operational Research, 2004, 155(2): 402-413
[136] Giffler B. and Thompson G.L. Algorithms for solving production scheduling problems. Operations Research, 1960, 8(4): 487-503
[137] Spears W.M. and Dejong K.A. On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, 1991: 230–236
[138] 周明, 孙树栋. 遗传算法原理及应用. 北京:国防工业出版社, 1999
[139] Barbosa H.J.C. A coevolutionary genetic algorithm for a game approach to structural optimization. In Proceedings of the seventh International Conference on Genetic Algorithms, 1997: 545-552
[140] McKay K.N., Safayeni F.R. and Buzacott J.A. The scheduler’s knowledge of uncertainty: the missing link. In Knowledge based production management systems. Elsevier Science Publishers, North-Holland, 1989
[141] Baker K.R.and Kanet J.J. Job shop scheduling with modified due dates. Journal of Operations Management, 1983, 4(1): 11-22
[142] Baker K.R. Sequencing rules and due date assignments in a job shop. Management Science, 1984, 30(9): 1093-1104
[143] Singer M. and Pinedo M. A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions, 1998, 30(2): 109-118
[144] Asano M. and Ohta H. A heuristic for job shop scheduling to minimize total weighted tardiness. Computers and Industrial Engineering, 2002, 42(2-4): 137-147
[145] Alcaide D., Rodriguez-Gonzalez A. and Sicilia J. An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns. European Journal of Operational Research, 2002, 140(2): 384-398
[146] 冯尚友. 多目标决策理论方法与应用. 上海:华中理工大学出版社, 1990
[147] Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithm. In: Proceedings of 1st Int. Conference on Genetic Algorithms and Their Applications, LawrenceErlbaum Associate, 1985: 93-100
[148] Horn J., Nafpliotis N. and Goldberg D. A niched pareto genetic algorithm for multi-objective optimization. In Proceedings of 1st IEEE Conference on Evolutionary Computation, 1994: 82-87
[149] Murata T., Ishibuchi H. and Tanaka H. Multi-objective genetic algorithm and its application to flow shop scheduling. Computers and Industrial Engineering, 1996, 30(4): 957–968
[150] Cochran J.K., Horng S.M. and Fowler J.W. A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers and Operations Research, 2003, 30(8): 1087–1102
[151] Rachamadugu R.V. and Morton T.E. Myopic heuristics for the single machine weighted tardiness problem. Working Paper 28-81-82, Graduate School of Industrial Administration, Carnegie Mellon University, 1981
[152] Leon, V. J., Wu, S.D. and Storer, R.H. A game-theoretic control approach for job shops in the presence of disruptions. International Journal of Production Research, 1994, 32(6): 1461-1476
[153] Demirkol E., Mehta S.V. and Uzsoy R. Benchmarks for shop scheduling problems. European Journal of Operational Research, 1998, 109(1): 137-141
[154] Wang B., Xi Y.G. and Gu H.Y. Terminal penalty rolling scheduling based on an initial schedule for single-machine scheduling problem. Computers and Operations Research, 2005, 32(11): 3059-3072
[155] Roundy R.O., Maxwell W.L., Herer Y.T., Tayur S.R. and Getaler A.W. A price-directed approach to real-time scheduling of production operations. IIE Trans., 1991, 23(2): 149-160
[156] Policella N., Smith S.F., Cesta A. and Oddi A. Generating robust schedules through temporal flexibility. Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS 04), Whistler CA, 2004
[157] McKay K.N. and Wiers V.C.S. Unifying the theory and practice of production scheduling. Journal of Manufacturing System, 1999, 18(4): 241-255
[158] Raman N. Minimum tardiness scheduling in flow shops: Construction and evaluation of alternative solution approaches. Journal of Operations Management, 1995, 12(2): 131-151
[2] Green G.I. and Appel L.B. An empirical analysis of job shop dispatch rule selection. Journal of Operations Management, 1981, 1(4): 197-203
[3] Hopp W.J. and Spearman M.L. Factory physics. Irwin/McGraw-Hill, Boston, 1996
[4] 王长军. 基于非合作博弈的生产调度建模与算法研究. 上海交通大学博士学位论文, 2006
[5] 唐国春, 张峰, 罗守成, 刘丽丽著. 现代排序论. 上海: 上海科学普及出版社, 2003
[6] Natalia V.S., Yuri N.S.and Frank W. Complexity of mixed shop scheduling problems: a survey. European Journal of Operational Research, 2000, 120(2): 343-351
[7] Jain A.S. and Meeran S. Deterministic Job shop scheduling: past, present and future. European Journal of Operational Research, 1999, 113(2): 390-434
[8] Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. and Shmoys D.B. Sequencing and scheduling: algorithms and complexity. In: Handbook in Operations Research and Management Science 4: Logistics of Production and Inventory, 1993
[9] Geoff L. Application of mathematical programming—before, now and after. Operation Research Society, 1985, 35(5): 347-356
[10] Taha H.A. Integer programming. New York: Academic Press, 1975
[11] Bellman R. Esogbue A.O. and Nabeshima I. Mathematical aspects of scheduling and application. Pergamon Press, New York, 1982
[12] Bellman R. Dynamic programming. Princeton University Press, USA, 1957
[13] Held M. and Karp R.M. A dynamic programming approach to sequencing problems. Journal of SIAM. 1962, 10(1): 196-210
[14] Carlier J. and Pinson E. An algorithm for solving the job-shop problem. Management Science, 1989, 35(2): 164-176
[15] Belouadah H., Posner M.E. and Potts C.N. Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Applied Mathematics, 1992, 36(3): 213-231
[16] Maccarthy B.L. and Liu J. Addressing the gap in scheduling research: a review of optimization and heuristic method in production scheduling. International Journal of Production Research, 1993, 31(1): 59-79
[17] Johnson S.M. Optimal two- and three-stage production schedules with set-up times. Naval Research Logistics Quarterly, 1954, 1: 61-68
[18] Blackstone J.H., Philips D.T. and Hogg G.T. A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 1982, 20(1): 27-46
[19] Kirkpatrick S., Gelatt C.D. and Vecchi M.P. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680
[20] Laarhoven P.J.M.V., Aarts E.H.L. and Lenstra J.K. Job shop scheduling by simulated annealing. Operations Research, 1992, 40(1): 113-125
[21] Satake T., Morikawa K., Takahashi K. and Nakamura N. Simulated annealing approach forminimizing the makespan of the general job-shop. International Journal of Production Economics, 1999, 60-61: 515-522
[22] Glover F. Tabu search - Part I. ORSA Journal on computing, 1989, 1(3): 190-206
[23] Glover F. Tabu search - Part II. ORSA Journal on computing, 1990, 2(1): 4-32
[24] Taillard E.D. Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing, 1994, 6(2): 108-117
[25] Nowicki E. and Smutnicki C. A fast taboo search algorithm for the job shop problem. Management Science, 1996, 42(2): 797-813
[26] Davis L. Job-shop scheduling with genetic algorithm. Proceedings of International Conference on Genetic Algorithm and their Application. 1985
[27] Groce F.D., Tadei R. and Volta G. A genetic algorithm for the job shop problem. Computers and Operations Research, 1995, 22(1): 15-24
[28] Binato S., Hery W.J., Loewenstern D.M. and Resende M.G.C. A GRASP for job shop scheduling. In: Ribeiro, C.C., Hansen, P. (Eds.), Essays and Surveys in Metaheuristics. Kluwer Academic Publishers, 2002
[29] Mattfeld D.C. and Bierwirth C. An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research. 2004, 155(2): 616–630
[30] 王凌, 郑大钟.求解同顺序加工调度问题的一种改进遗传算法. 系统工程理论与实践, 2002, 22(6): 74-79
[31] 李岩, 吴智铭. 基于约束逻辑规划和遗传算法的柔性调度. 控制与决策, 2002, 17(3): 297-300
[32] 杨红红. 遗传算法在制造系统计划与调度优化中的应用. 上海交通大学博士学位论文, 2002
[33] 顾幸生, 郑璐, 李平, 张伟. 不确定性条件下存储时间有限型 Flow Shop 问题的提前/拖期调度研究. 华东理工大学学报, 2004, 30(3: 322-327
[34] Fonseca C.M. and Fleming P.J. An overview of evolutionary algorithm in multi-objective optimization. Evolutionary Computation, 1995, 3(1): 1-16
[35] Tamaki H., Kita H. and Kobayashi S. Multiobjective optimization by genetic algorithm: a review. In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 1996: 517–522
[36] Horn J. Multicriterion decision making. The Handbook of Evolutionary Computation. Oxford University Press, New York, 1997, F1.9: 1-15
[37] Kiran A.S. and Smith M.L. Simulation studies in Job shop scheduling-I a survey. Computer and Industry Enginieering, 1984, 8(2): 87-93
[38] Wu S.Y.D. and Richard A.W. An application of discrete-event simulation to on-line control and scheduling in flexible manufacturing. International Journal of Production Research, 1989, 27(9): 1603-1623
[39] Ovacik I.M. and Uzsoy R. Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times. International Journal of Production Research, 1994, 32(6): 1243-1263
[40] Ovacik I.M. and Uzsoy R., Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times. International Journal of Production Research, 1995, 33(11): 3173-3192
[41] Ovacik I.M. and Uzsoy R. Decomposition methods for complex factory scheduling problems. Boston/Dordrecht/London: Kluwer Academic Publishers, 1997
[42] Luh P.B. and Hoitomt D.J. Scheduling of manufacturing systems using the lagrangian relaxation technique. IEEE Transactions on Automatic Control, 1993, 38(7): 1066-1079
[43] Adams J., Balas E. and Zawack D. The shifting bottleneck procedure for job shop scheduling. Management Science, 1988, 34(3): 391-401
[44] Wang J. and Luh P.B. A combined Lagrangean relaxation relation and dynamic programming algorithm for job shop scheduling. In Proceedings 5th International Conference on Computer Integrated Manufacturing Automatic Technology, Grenoble, France, May 1996: 3-8
[45] Chen D., Liu F. and Luh P. B. Scheduling job shops with uncertainties. Proceedings of the 36th Conference on Decision and Control, San Diego, California USA, 1997
[46] 席裕庚. 预测控制. 国防工业出版社, 1993
[47] 席裕庚. 动态不确定环境下广义控制问题的预测控制. 控制理论与应用, 2000, 17(5): 665-670
[48] Fang J. and Xi Y.G. A rolling horizon job shop rescheduling strategy in the dynamic environment. The International Journal of Advanced Manufacturing Technology. 1997, 13(3): 227-232
[49] 方剑, 席裕庚. 基于遗传算法的滚动调度策略. 控制理论与应用. 1997, 14(4): 589-594
[50] 王冰. 滚动时域调度方法及其性能分析研究. 上海交通大学博士学位论文, 2005
[51] Carlier J. The one-machine sequencing problem. European Journal of Operational Research, 1982, 11(1): 42-47
[52] Dauzere-Peres S. and Lasserre J. A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research 1993, 31(4): 923-932
[53] Applegate D. and Cook W. A computational study of the job shop scheduling problem. ORSA Journal of Computing, 1991, 3(2): 149-156
[54] Balas E., Lenstra J. and Vazacopoulos A. The one-machine problem with delayed precedence constraints and its use in the job shop scheduling. Management Science 1995, 41(1): 94-109
[55] Ramudhin A. and Philip M. The generalized shifting bottleneck procedure. European Journal of Operational Research. 1996, 93(1): 34-48
[56] Pinedo M. and Singer M. A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research and Logistics 1999, 46: 1-17
[57] Singer M. Decomposition methods for large job shops. Computers and Operations Research 2001, 28(3): 193-207
[58] Suresh V. and Chandhuri D. Dynamic scheduling-A survey of research. International Journal of Production Economics, 1993, 32(1): 53-63
[59] Vieira G.E., Herrmann J.W. and Lin E. Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1): 39-62
[60] Pinedo M. Scheduling: theory, algorithms and systems. Prentice-Hall, Englewood Cliffs, 1995
[61] Church L.K. and Uzsoy R. Analysis of periodic and event-driven rescheduling policies in dynamic shops. International Journal of Computer Integrated Manufacturing, 1992, 5(3): 153-163
[62] Kamoun H. and Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacturing systems. European Journal of Operational Research, 1993, 70(3): 350-364
[63] Hall N.G. and Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 1996, 44(3): 510-525
[64] Markowitz, D.M. and Lawrence M.W. Heavy traffic analysis of dynamic cyclic policies: a unified treatment of the single machine scheduling problem. Operations Research, 2001, 49(2): 246-270
[65] Abumaizar R.J. and Svestka J.A. Rescheduling job shops under disruptions. International Journal ofProduction Research, 1997, 35(7): 2065-2082
[66] Yamamoto M. and Nof S.Y. Scheduling/rescheduling in the manufacturing operating system environment. International Journal of Production Research, 1985, 23(4): 705-722
[67] Wu S.D., Storer R.H. and Chang P.C. One-machine rescheduling heuristics with efficiency and stability as criteria. Computers and Operations Research, 1993, 20(1): 1-14
[68] Cowling P.I. and Johansson M. Using real time information for effective dynamic scheduling, European Journal of Operational Research, 2002, 139(2): 230-244
[69] Sabuncuoglu I. and Karabuk S. Rescheduling frequency in an FMS with uncertain processing times and unreliable machines. Journal of Manufacturing Systems, 1999, 18(4): 268-283
[70] Vollmann T.E., Berry W.L. and Whybark D.C. Manufacturing planning and control systems, fourth edition, Irwin/McGraw-Hill, New York, 1997
[71] Jain A.K. and Elmaraghy H.A. Production scheduling/rescheduling in flexible manufacturing. International Journal of Production Research, 1997, 35(1): 281-309
[72] Henning G.P. and Cerda J. An expert system for predictive and reactive scheduling of multiproduct batch plants. Latin American Applied Research, 1995, 25: 187-198
[73] Vieira G.E., Herrmann J.W. and Lin E. Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies. International Journal of Production Research, 2000, 38(8): 1899-1915
[74] Vieira G.E., Herrmann J.W. and Lin E. Predicting the performance of rescheduling strategies for parallel machine systems. Journal of Manufacturing Systems, 2000, 19(4): 256-266
[75] Shafaei R. and Brunn P. Workshop scheduling using practical (inaccurate) data - Part 2: An investigation of the robustness of scheduling rules in a dynamic and stochastic environment. International Journal of Production Research, 1999, 37(18), 4105-4117
[76] Kempf K.G. Intelligently scheduling semiconductor wafer fabrication. Intelligent Scheduling, Zweben M. and Fox M.S. ed., Morgan Kaufmann Publishers, San Francisco, 1994
[77] Smith S. Reactive scheduling systems. Intelligent scheduling systems, Brown D.E. and Scherer W.T., ed., Kluwer Press, 1995
[78] Monostori L., Szelke E. and Kadar B. Management of changes and disturbances in manufacturing systems. Annual Reviews in Control, Pergamon Press, Elsevier Science, 1998, 22: 85-97
[79] Sabuncuoglu I. and Bayiz M. Analysis of reactive scheduling problems in a Job shop environment. European Journal of Operational Research, 2000, 126(3): 567-586
[80] Sun J. and Xue D. A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources. Computers in Industry, 2001, 46(2): 189-207
[81] Perkins J.R. and Kumar P.R. Stable distributed, real-time scheduling of flexible manufacturing/assembly/disassembly systems. IEEE Transactions on Automatic Control, 1989, 34(2): 139-148
[82] Chase C. and Ramadge P.J. On real-time scheduling policies for flexible manufacturing systems. IEEE Transactions on Automatic Control, 1992, 37(4): 491-496
[83] Huang Y.G., Kanal L.N. and Tripathi S.K. Reactive scheduling for a single machine: Problem definition, analysis, and heuristic solution. International Journal of Computer Integrated Manufacturing, 1990, 3(1): 6-12
[84] Szelke E. and Kerr R. Knowledge-based reactive scheduling. Production Planning & Control, 1994, 5(2): 124-145
[85] Herrmann J.W., Lee C.Y. and Hinchman J. Global job shop scheduling with a genetic algorithm.Production and Operations Management, 1995, 4(1): 30-45
[86] Li R.-K., Shyu Y.-T. and Adiga S. A heuristic rescheduling algorithm for computer-based production scheduling systems. International Journal of Production Research, 1993, 31(1): 1815-1826
[87] Kim M.H. and Kim Y.-D. Simulation-based real-time scheduling in a flexible manufacturing system. Journal of Manufacturing Systems, 1994, 13(2): 85-93
[88] Bierwirth C. and Mattfeld D.C. Production scheduling and rescheduling with genetic algorithms. Evolutionary Computation, 1999, 7(1): 1-17
[89] Wu H.-H., and Li. R.-K. A new rescheduling method for computer based scheduling systems. International Journal of Production Research, 1995, 33(8): 2097-2110
[90] Bean J.C., Birge J.R., Mittenthal J. and Noon C.E. Match up scheduling with multiple resources, release dates, and disruptions. Operation Research, 1991, 39(3): 470-483
[91] Selim A.M. and Gorgulu E. Match-up scheduling under a machine breakdown. European Journal of Operational Research, 1999, 112(1): 81-97
[92] Leon V.J., Wu S.D. and Storer R.H. Robustness measures and robust scheduling for job shops. IIE Transactions, 1994, 26(5): 32-43
[93] Mehta S.V. and Uzsoy R. Predictable scheduling of a job shop subject to breakdowns. IEEE Transactions on Robotics and Automation, 1998, 14(3): 365-378
[94] Mehta S.V. and Uzsoy R. Predictable scheduling of a single machine subject to breakdowns. International Journal of Computer Integrated Manufacturing, 1999, 12(1): 15-38
[95] O’Donovan R., Uzsoy R. and McKay K.N. Predictable scheduling of a single machine with breakdowns and sensitive jobs. International Journal of Production Research, 1999, 37(18): 4217-4233
[96] Byeon E.S., Wu S.D. and Storer R.H. Decomposition heuristics for robust job shop scheduling. IEEE Trans on Robotics and Automation, 1998, 14(2): 303-313
[97] Wu S.D., Byeon E.S. and Storer R.H. A Graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Operations Research, 1999, 47(1): 113-124
[98] Kouvelis P. and Yu G. Robust discrete optimization and its applications. Kluwer Academic Publishers, 1997
[99] Daniels R.L. and Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41(2): 363-376
[100] Kouvelis P., Daniels R.L. and Vairaktarakis G. Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Transactions, 2000, 32(5): 421-432
[101] Yang J. and Yu G. On the robust single machine scheduling problem. Journal of Combinatorial Optimization, 2002, 6(1): 17-33
[102] 李建更. 关于最优调度鲁棒性的研究. 南开大学博士学位论文, 2000
[103] 李建更, 涂菶生. 某些调度问题区间摄动鲁棒性研究. 自动化学报, 2001, 27(1): 24-30
[104] 李建更, 涂菶生. 一类 Flow shop 调度问题最优调度区间摄动鲁棒性. 控制理论与应用, 2004, 21(1): 25-29
[105] Herrmann J. W. A genetic algorithm for minimax optimization problems. In Angeline P. J. et al., editor, Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, 1999, 2: 1099-1103
[106] Jensen M.T. Finding worst-case flexible schedules using coevolution. In: Proc. of the Genetic and Evolutionary Computation Conference. Spector, L.et al. (Ed.). GECCO 2001, July 7-11, San Francisco, USA: 2001: 1144-1151
[107] Pinedo M. Stochastic scheduling with release dates and due dates. Operations Research, 1983, 31(3): 559-572
[108] Kanet J.J. Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics Quarterly, 1981, 28: 643-651
[109] Hall N.G. and Posner M.E. Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Operations Research, 1991, 39(5): 836-846
[110] Hall N.G., Kubiak W. and Sethi S.P. Earliness-tardiness scheduling problems, II: deviation of completion times about a restrictive common due date. Operations Research, 1991, 39(5): 847-856
[111] Baker K.R. and Scudder G.D. Sequencing with earliness and tardiness penalties: a review. Operations Research, 1990, 38(1): 22-36
[112] Ow P.S. and Morton T.E. The single machine early/tardy problem. Management Science, 1989, 35(2): 177-191
[113] Sivrikaya-Serifoglu F. and Ulusoy G. Parallel machine scheduling with earliness and tardiness penalties. Computers and Operations Research, 1999, 26(8): 773-787
[114] 玄光男, 程润伟著. 遗传算法与工程设计. 科学出版社, 2000
[115] 玄光男, 程润伟著. 于歆杰 周根贵译. 遗传算法与工程优化. 清华大学出版社, 2004
[116] Lenstra J., Rinnooy K.A and Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1:343-362
[117] Holland J.H. Adaptation in natural and artificial Systems: An introductory analysis with applications to biology, control and artificial intelligence. 2nd ed. MIT Press, Cambridge, Massachusetts, 1992
[118] Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Addison-Wesley, 1989
[119] Michalewicz Z. Genetic algorithm + Data structure = Evolution programs. Second Edition, Springer-Verlag, 1994
[120] Cheng R., Gen M. and Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers and Industrial Engineering, 1996, 36(2): 343-364
[121] Falkenauer E. and Bouffoix S. A genetic algorithm for job shop. In: Proceedings of the 1991 IEEE International Conference on Robotics and Automation, 1991: 824-849
[122] B?ck T. Selective, pressure in evolutionary algorithms: A characterization of selection mechanisms. In Proceedings of the first IEEE Conference on Evolutionary Computation, IEEE Press, 1994, 1: 57-62
[123] Grefenstette J.J. Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics. 1986, 16(1): 122-128
[124] Mikkel T. Jensen. Robust and flexible scheduling with evolutionary computation. PhD Dissertation, Department of Computer Science University of Aarhus Denmark, 2001
[125] 王凌. 车间调度及遗传算法. 清华大学出版社, 2003
[126] Gen M., Tsujimura Y. and Kubota E. Solving job-shop scheduling problem using genetic algorithms. In proceedings of the 16th International Conference on Computer and Industrial Engineering, Ashikaga, Japan, 1994: 576-579
[127] Holsapple C., Jacob V., Pakath R. and Zaveri J. A genetic-based hybrid scheduler for generated static schedules in flexible manufacturing contexts. IEEE Trans On Systems, Man, and Cybernetics, 1993, 23(4): 953-971
[128] Davis L. Job shop scheduling with genetic algorithm. In Proceedings of the First InternationalConference on Genetic Algorithms (Edited by Grefenstette). Lawrence Erlbaum Associates, Hillsdale, NJ, 1985: 136-140
[129] Nakano R. and Yamada T. Conventional genetic algorithms for job-shop problems. In Proceedings of the Fourth International Conference on Genetic Algorithms (Edited by Belew and Booker). Morgan Kaufman, San Mateo, Calif, 1991: 477-479
[130] Dorndorf U. and Pesch E. Evolution based learning in a job shop scheduling environment. Computers and Operations Research, 1995, 22(1): 25-40
[131] Tamaki H. and Nishikawa Y. A paralleled genetic algorithm based on a neighborhood model and its application to the job shop scheduling. In Proceedings of the Second International Conference on Parallel Problem Solving from Nature, Elsevier Science Publishers North-Holland, 1992: 573-582
[132] Yamada T. and Nakano R. A genetic algorithm applicable to large-scale job-shop problems. In Proceedings of the Second International Conference on Parallel Problem Solving from Nature, Elsevier Science Publishers North-Holland, 1992: 281-290
[133] Bean J.C. Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on Computing, 1994, 6(2): 154-160
[134] Riezebos J. and Gaalman G.J.C. Time lag size in multiple operations flow shop scheduling heuristics, European Journal of Operational Research. 1998, 105(1): 72-90
[135] Fleszar Krzysztof and Hindi Khalil S. Solving the resource-constrained project scheduling problem by a variable neighbourhood search. European Journal of Operational Research, 2004, 155(2): 402-413
[136] Giffler B. and Thompson G.L. Algorithms for solving production scheduling problems. Operations Research, 1960, 8(4): 487-503
[137] Spears W.M. and Dejong K.A. On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, 1991: 230–236
[138] 周明, 孙树栋. 遗传算法原理及应用. 北京:国防工业出版社, 1999
[139] Barbosa H.J.C. A coevolutionary genetic algorithm for a game approach to structural optimization. In Proceedings of the seventh International Conference on Genetic Algorithms, 1997: 545-552
[140] McKay K.N., Safayeni F.R. and Buzacott J.A. The scheduler’s knowledge of uncertainty: the missing link. In Knowledge based production management systems. Elsevier Science Publishers, North-Holland, 1989
[141] Baker K.R.and Kanet J.J. Job shop scheduling with modified due dates. Journal of Operations Management, 1983, 4(1): 11-22
[142] Baker K.R. Sequencing rules and due date assignments in a job shop. Management Science, 1984, 30(9): 1093-1104
[143] Singer M. and Pinedo M. A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions, 1998, 30(2): 109-118
[144] Asano M. and Ohta H. A heuristic for job shop scheduling to minimize total weighted tardiness. Computers and Industrial Engineering, 2002, 42(2-4): 137-147
[145] Alcaide D., Rodriguez-Gonzalez A. and Sicilia J. An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns. European Journal of Operational Research, 2002, 140(2): 384-398
[146] 冯尚友. 多目标决策理论方法与应用. 上海:华中理工大学出版社, 1990
[147] Schaffer J.D. Multiple objective optimization with vector evaluated genetic algorithm. In: Proceedings of 1st Int. Conference on Genetic Algorithms and Their Applications, LawrenceErlbaum Associate, 1985: 93-100
[148] Horn J., Nafpliotis N. and Goldberg D. A niched pareto genetic algorithm for multi-objective optimization. In Proceedings of 1st IEEE Conference on Evolutionary Computation, 1994: 82-87
[149] Murata T., Ishibuchi H. and Tanaka H. Multi-objective genetic algorithm and its application to flow shop scheduling. Computers and Industrial Engineering, 1996, 30(4): 957–968
[150] Cochran J.K., Horng S.M. and Fowler J.W. A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers and Operations Research, 2003, 30(8): 1087–1102
[151] Rachamadugu R.V. and Morton T.E. Myopic heuristics for the single machine weighted tardiness problem. Working Paper 28-81-82, Graduate School of Industrial Administration, Carnegie Mellon University, 1981
[152] Leon, V. J., Wu, S.D. and Storer, R.H. A game-theoretic control approach for job shops in the presence of disruptions. International Journal of Production Research, 1994, 32(6): 1461-1476
[153] Demirkol E., Mehta S.V. and Uzsoy R. Benchmarks for shop scheduling problems. European Journal of Operational Research, 1998, 109(1): 137-141
[154] Wang B., Xi Y.G. and Gu H.Y. Terminal penalty rolling scheduling based on an initial schedule for single-machine scheduling problem. Computers and Operations Research, 2005, 32(11): 3059-3072
[155] Roundy R.O., Maxwell W.L., Herer Y.T., Tayur S.R. and Getaler A.W. A price-directed approach to real-time scheduling of production operations. IIE Trans., 1991, 23(2): 149-160
[156] Policella N., Smith S.F., Cesta A. and Oddi A. Generating robust schedules through temporal flexibility. Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS 04), Whistler CA, 2004
[157] McKay K.N. and Wiers V.C.S. Unifying the theory and practice of production scheduling. Journal of Manufacturing System, 1999, 18(4): 241-255
[158] Raman N. Minimum tardiness scheduling in flow shops: Construction and evaluation of alternative solution approaches. Journal of Operations Management, 1995, 12(2): 131-151