|
Abstract: The dynamic job shop scheduling with uncertain arriving time is studied, and the objective is to minimize total tardiness of all jobs. When rescheduling is frequent, the computational efficiency of the scheduling algorithm is necessarily high. Based on the rolling horizon decomposition, the critical operation set is denoted. A hybrid genetic algorithm is proposed to determine the critical operation set as well as optimizing total tardiness. The hybrid scheduler is used to convert the chromosome into partially feasible schedule, and the improved modified operation rule is used to determine the sequence of the remaining operations out of the chromosome. Then the fitness is evaluated by the objective value of the complete scheduling for the total operations to process. The simulation results of many instances show that the proposed algorithm significantly improves the computational efficiency compared with the genetic algorithm based on the complete operation set, and the performance of scheduling is satisfying.
Key words: Dynamic job shop scheduling Rolling horizon decomposition Critical operation set Genetic algorithm
CLC No:
TP301
国家自然科学基金(60474002, 60504026)和国家高技术研究发展计划(863计划, 2006AA04Z173)资助项目.
Received
20070524,
received
in
revised
form
20071210
|
| References
[1] CHURCH L K, UZSOY R. Analysis of periodic
and event-driven rescheduling policies in dynamic shops [J].
International Journal of Computer Integrated
Manufacturing, 1992, 5(3): 153-163.
[2] OVACIK I M, UZSOY R. Rolling horizon algorithms for a single-machine
dynamic scheduling problem with sequence-dependent setup times[J].
International Journal of Production Research, 1994, 32(6): 1 243-1 263.
[3] FANG J, XI Y G. Rolling horizon job shop rescheduling strategy in
the dynamic environment[J]. International Journal of Advanced
Manufacturing Technology, 1997, 13(3): 227-232.
[4] WANG B, XI Y G, GU H Y. Terminal penalty rolling scheduling based on
an initial schedule for single- machine scheduling problem [J]. Computers
and Opera- tions Research, 2005, 32(11): 3 059-3 072.
[5] BYEON E S, WU S D, STORER R H. Decomposition heuristics for robust
job shop scheduling [J]. IEEE Trans. on Robotics and
Automation, 1998, 14(2): 303-313.
[6] WU S D, BYEON E S, STORER R H. A graph-theoretic decomposition of
the job shop scheduling problem to achieve scheduling
robustness[J]. Operations Research, 1999, 47(1): 113-124.
[7] POLICELLA N, SMITH S F, CESTA A, et al. Genera- ting robust
schedules through temporal flexibility [C]//Proceedings 14th
International Conference on Automated Planning and Scheduling (ICAPS
04), Whistler CA, 2004: 209-218.
[8] SUN Zhijun, ZHU Jianying, PAN Quanke. Genetic algorithm based
approach to the intelligent optimum scheduling of multi-resources in the
dynamic environment[J]. Chinese Journal of Mechanical Engineering ,
2002, 38(4): 120-125.
[9] HU Yongmei, JIA Lei, LI Qiqiang. Recognition method of job rolling
scheduling based on dynamic rough dets[J]. Chinese Journal of Mechanical
Engineering, 2005, 41(3): 67-71.
[10] WANG Ling. Shop scheduling with genetic algorithms[M].
Beijing: Tsinghua University Press, 2003.
[11] MICHALEWICZ Z. Genetic algorithm + data structure evolution
programs [M]. 2nd ed. New York: Springer, 1994.
[12] HOLLAND J H. Adaptation in natural and artificial systems: an
introductory analysis with applications to biology, control and
artificial intelligence [M]. 2nd ed. Cambridge, Massachusetts: MIT Press,
1992.
[13] SPEARS W M, DEJONG K A. On the virtues of parameterized uniform
crossover [C]//Proceedings of the Fourth International Conference on
Genetic Algorithms, 1991: 230-236.
[14] BAKER K R. Sequencing rules and due date assignments in a job
shop[J]. Management Science, 1984, 30(9): 1 093-1 104.
[15] RAMAN N. Minimum tardiness scheduling in flow shops: Construction
and evaluation of alternative solution approaches[J]. Journal of
Operations Management, 1995, 12(2): 131-151.
[16] GIFFLER B, THOMPSON G L. Algorithms for solving production
scheduling problems[J]. Operations Research, 1960, 8(4): 487-503.
[17] BIERWIRTH C, MATTFELD D C. Production scheduling and rescheduling
with genetic algorithm[J]. Evolutionary Computation, 1999, 7(1): 1-17.
[18] DEMIRKOL E, MEHTA S V, UZSOY R. Benchmarks for shop scheduling
problems[J]. European Journal of Operational
Research, 1998, 109(1): 137-141.
|