大规模生产调度问题的研究现状与展望

• 论文 •

大规模生产调度问题的研究现状与展望

金锋，吴澄

清华大学自动化系，北京 100084

收稿日期:2004-11-08 修回日期:2005-01-17 出版日期:2006-02-15 发布日期:2006-02-25
基金资助:
国家973计划资助项目（2002CB312202）；国家自然科学基金资助项目(60574077)。

Research status and prospects for massive production scheduling

JIN Feng, WU Cheng

Dep. of Automation, Tsinghua Univ., Beijing 100084, China

Received:2004-11-08 Revised:2005-01-17 Online:2006-02-15 Published:2006-02-25
Supported by:
Project supported by the National Key Basic R&D Program,China(No.2002CB312202)and the National Natural Science Foundation, China(No.60574077).

摘要/Abstract

摘要： 为解决大多数已有调度算法无法直接应用于大规模生产调度的问题，以典型生产调度问题为背景，综述了现阶段已有大规模生产调度问题的算法。分析了大规模生产调度问题规模增长的因素，重点介绍了基于问题分解的各类方法、拉格朗日松弛/分解法及智能优化算法。在此基础上，展望了大规模生产调度问题的研究发展趋势。

关键词: 大规模生产调度, 问题分解, 拉格朗日松弛/分解, 智能优化算法

Abstract: At present most scheduling algorithms cannot be directly applied in massive prod uction scheduling, based on the typical production scheduling problems, existing algorithms for massive production scheduling were summarized. The influencing f actors for scale increase in massive production scheduling problem were analyzed . Then some of the typical algorithms were introduced, such as algorithms based on problem decomposition, Lagrangian relaxation/decomposition and intelligent op timization algorithms. Finally, prospects for massive production scheduling algo rithm were presented.

Key words: massive production scheduling, problem decomposition, Lagrangi an relaxation/decomposition, intelligent optimization algorithms

中图分类号:

F406.2

金锋，吴澄. 大规模生产调度问题的研究现状与展望[J]. .

JIN Feng, WU Cheng. Research status and prospects for massive production scheduling[J]. .

参考文献

［1］ JOHNSON S M.Optimal two-and three-stage production schedules with setup times included［J］.Naval Research Logistics Quarterly,1954,1(1):61-68.

[2] LENSTRA J K,RINNOY K A H G,BRUCKER P.Complexity of machine scheduling problems［A］.Studies in Integer Programming［C］.New York,NY,USA:North-Holland Publishing Company,1977.343-362.

[3] WANG Ling.Shop scheduling with genetic algorithms［M］.Beijing:Tsinghua University Press,2003(in Chinese).［王凌.车间调度及其遗传算法［M］.北京:清华大学出版社，2003.］

[4] BITRAN G R,HAAS E A,HAX A C.Hierarchical production planning: a single stage system［J］.Operations Research,1981,29(4):717-743.

[5] BASSETT M H,DAVE P,DOYLE III F J,et al.Perspectives on model based integration of process operations［J］.Computer & Chemical Engineering,1996,20(6-7):821-844.

[6] BASSETT M H,JOSEPH F P,GINTARAS V R.Decomposition techniques for the solution of large-scale scheduling problems［J］.AIChE Journal,1996,42(12):3373-3387.

[7] WU D,IERAPETRITOU M G.Decomposition approaches for the efficient solution of short-term scheduling problems［J］.Computers & Chemical Engineering,2003,27(8-9):1261-1276.

[8] CHU C,PORTMANN M C,PROTH J M.A splitting-up approach to simplify job-shop scheduling problems［J］.International Journal of Production Research,1992,30(4):859-70.

[9] SUN D,BATTA R.Scheduling larger job shops: a decomposition approach［J］.International Journal of Production Research,1996,34(7):2019-2033.

[10] SANNOMIYA N,IIMA H.Genetic algorithm approach to an optimal scheduling problem for a large-scale complex manufacturing system［A］.Proceedings of the IEEE International Conference on Systems,Man and Cybernetics［C］.NJ,USA:IEEE,1999,3:III-622 - III-627.

[11] ROSLF J,HARJUNKOSKI I,WESTERLUND T,et al.A short-term scheduling problem in the paper-converting industry［J］.Computers & Chemical Engineering,1999,23(12):S861-S864.

[12] ROSLF J,HARJUNKOSKI I,WESTERLUND T,et al.Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure［J］.European Journal of Operational Research,2002,138(1):29-42.

[13] WERNER F,WINKLER A.Insertion techniques for the heuristic solution of the job shop problem［J］.Discrete Applied Mathematics,1995,58(2):191-211.

[14] KIM Y,WOO K,IUABA A,et al.FMS scheduling based on timed Petri net model and RTA* algorithm［A］.Proceedings of 2001 IEEE International Conference on Robotics and Automation(ICRA)［C］.NJ,USA:IEEE,2001.848-853.

[15] KIM Y, IUABA A,SUZUKI T,et al.Hierarchical scheduling for large-scale production system based on continuous and timed Petri net model［A］.Proceedings of the 41st SICE Annual Conference［C］.Tokyo,Japan:The Society of Instrument and Control Engineers(SICE),2002.268-271.

[16] FISHER M L.The lagrangian relaxation method for solving integer programming problems［J］.Management Science,1981,27(1):1-18.

[17] FISHER M L.An applications oriented guide to lagrangian relaxation［J］.Interfaces,1985,15(2):10-21.

[18] GUIGNARD M,KIM S.Lagrangian decomposition: a model yielding stronger Lagrangian bounds［J］.Mathematical Programming,1987,39(2):215-228.

[19] WU Qinglie,XU Nanrong.A decomposition method for solving the integer large-scale optimization problem［J］.Journal of Southeast University,1996,26(3):119-125(in Chinese).［吴清烈，徐南荣.大规模含整变量优化问题的一种分解方法［J］.东南大学学报，1996,26(3):119-125.］

[20] WANG J,LUH P B,ZHAO X,et al.An optimization-based algorithm for job shop scheduling［J］.Sadhana - Academy Proceedings in Engineering Sciences,1997,22(2):241-256.