进化计算在生产线调度研究中的现状与展望

摘要/Abstract

摘要： 描述了典型生产线调度类型，并分析了其复杂性、不确定性、多目标和多约束等特点；简要介绍了进化计算的思想、优点；围绕其应用核心——遗传编码和操作，分类评述了进化计算在单机、并行机、流水线、可重入式生产线、作业和混合生产线等调度问题中的应用情况；并从调度模型和进化计算两方面探讨了面向实际生产线调度的研究前景。

关键词: 进化计算, 生产线调度, 遗传, 进化, 优化, 编码

Abstract: The typical production scheduling problems are formulated and the research difficulties such as complexity, uncertainty, multi objectives and multi constraints are analyzed. Then evolutionary computation (EC) is introduced mainly on its inspiration, virtues and implementation issues. With the focuses on genetic encoding and operators, the representative applications of EC to production scheduling problems are detailedly overviewed in such fields as single machine-, parallel machine-, flowshop-, re-entrance, jobshop-, hybrid production-scheduling and so on. The perspective of EC applied to practical scheduling problems is suggested from both scheduling model and EC theory points of view finally.

Key words: evolutionary computation, production scheduling, inherit, evolve, optimization, encoding

中图分类号:

尹文君，刘民，吴澄. 进化计算在生产线调度研究中的现状与展望[J]. .

YIN Wen-jun，LIU Min，WU Cheng. Currnet Staus and Prospect of Evolutionary Computation Applied to 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):61-68.

[2] BCK T, HAMMEL U， et al. Evolutionary computation: comments on the history and current state [J]. IEEE Transactions on Evolutionary Computation,1997, 1(1):3-17.

[3]DAVIS L. Job-shop scheduling with genetic algorithm[A]. Proc. of Int'1 Conf. on Genetic Algorithms and their Applications[C]. 1985.136-149.

[4]CONWAY R V, MAXWELL W L， et al. Theory of scheduling[M]. Addison-Wesley, Reading, Massachusetts, 1967.

[5] HOLLAND J H. Adaptation in natural and artificial systems[M]. Univ. of Michigan Press, 1975.

[6] KOZA J R. Genetic Programming: On the programming of computers by means of natural selection[M]. MIT Press,1992.

[7]FOGEL L J, OWENS A J， et al. Artificial intelligence through simulated evolution[M]. New York:Wiley, 1966.

[8]Rechenberg I. Evolutionsstrategies: Optimerung technischer systemenach prinzipien der biologischen evolution[M]. Frommann Hlozboog Verlag,1973.

[9]SCHWEFEL H P. Kybernetische evolution als strategic der experimentelen forschung in der stromung-stechnik[D]. Technical University of Berlin, 1965.

[10]HOLLAND J H. Processing and processors for schemata[A]. In: Jacks EL[C]. Associative Information Processing， New York: Elsevier, 1971.127-146.

[11] GUPTA M C, et al. Minizing flow time variance in a single machine system using genetic algorithms[J]. European Journal of Production Research, 1993，70(3): 289-303.

[12] RUBIN P A ，RAGATZ G L. Scheduling in a sequence dependent setup environment with genetic search[J]. Comput. Oper. Res., 1995, 22(1): 85-99.
[13]LIU J Y， TANG L X. A modified genetic algorithm for single machine scheduling[J]. Computer & Industrial Engineering, 1999,37(1): 43-46.
[14]刘民. 遗传算法及其在生产线调度问题中的应用研究 [D]. 北京:清华大学自动化系,1999.

[15] LIU M， WU C. A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines[J]. Artificial Intelligence in Engineering, 1999,13(4): 399-403.

[16]刘民,吴澄,蒋新松. 进化规划方法在并行多机调度问题中的应用 [J]. 清华大学学报,1998,38(8):100-103.

[17]刘民，吴澄.进化规划方法在最小化拖期任务数并行机调度问题中的应用［J］.电子学报，1997，27(7)：132-134.

[18]刘民,吴澄, 杨英杰.最小化完工时间并行机调度问题的一种基于组合规则的遗传算法[A], 第五届中国计算机集成制造系统（CIMS）学术会议论文集 [C]. 成都：第五届中国计算机集成制造系统学术会议， 1998.5-114.

[19]刘民，吴澄. 解决并行多机提前/拖后调度问题的混合遗传算法方法 [J]. 自动化学报, 2000, 26(2): 258-262.

[20]黄宇纯,王树青,王骥程. Flow-shop调度问题的遗传启发式算法 [J]. 信息与控制,1996,(8): 212-216.

[21]SYSWERDA G. Scheduling optimization using genetic algorithm. Handbook of Genetic Algorithms, Davis L(ed)[M]. New