一类流水型知识化制造单元调度的自进化算法

中国机械工程 ›› 2011, Vol. 22 ›› Issue (7): 830-835.

一类流水型知识化制造单元调度的自进化算法

李文超1,2;严洪森1

1.东南大学复杂工程系统测量与控制教育部重点实验室, 南京，210096

2.江苏大学，镇江，212013

出版日期:2011-04-10 发布日期:2011-04-15
基金资助:
国家自然科学基金资助项目(60934008，50875046)
National Natural Science Foundation of China（No. 60934008，50875046）

A Self-evolution Algorithm for Scheduling a Flow-shop-like Knowledgeable Manufacturing Cell

Li Wenchao1,2;Yan Hongsen1

1.Key Laboratory of Measurement and Control of CSE, Ministry of Education, Southeast University, Nanjing, 210096

2.Jiangsu University, Zhenjiang,Jiangsu, 212013

Online:2011-04-10 Published:2011-04-15
Supported by:
National Natural Science Foundation of China（No. 60934008，50875046）

摘要/Abstract

摘要：

机器数大于2的流水型知识化制造单元调度属于NP完全问题，至今尚无完全有效的算法。针对该类问题的自身结构特性，提出一种具备学习能力的自进化算法。该算法采用强化学习中值迭代策略，在运行中能够从环境中获取相应知识，提高其搜索能力。提出一种混合核支持向量机对值函数进行逼近，以解决学习过程中状态过多的问题。数值仿真实验表明，算法对该类问题具有很好的学习进化能力。



关键词:

知识化制造单元, 自进化, 强化学习, 支持向量机

Abstract:

The flow-shop-like knowledgeable manufacturing cell (whose machine number is greater than 2) scheduling is a NP-complete problem and has not a completely valid algorithm for it until now. A self-evolution algorithm with learning ability was proposed according to its structure and characteristics. By adopting the value iterative strategies of reinforcement learning, the algorithm can absorb the corresponding knowledge from its environment during its running and improve its search ability. The approximation of value function is completed by use of the SVM with a hybrid kernel to avoid the too many states in learning process. Numerical experiments show that the algorithm has excellent performance of learning and evolution for the problem.

Key words:

knowledgeable manufacturing cell, self-evolution, reinforcement learning, support vector machine(SVM)

中图分类号:

TP301

李文超, 严洪森.

一类流水型知识化制造单元调度的自进化算法

[J]. 中国机械工程, 2011, 22(7): 830-835.

LI Wen-Chao, YAN Hong-Sen.

A Self-evolution Algorithm for Scheduling a Flow-shop-like Knowledgeable Manufacturing Cell

[J]. China Mechanical Engineering, 2011, 22(7): 830-835.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.cmemo.org.cn/CN/

http://www.cmemo.org.cn/CN/Y2011/V22/I7/830

参考文献

[1]严洪森[1],刘飞[2].知识化制造系统——新一代先进制造系统[J].计算机集成制造系统,2001,7(8):7-11.
[2]Yan Hongsen. A New Complicated Knowledge Representation Approach Based on Knowledge Meshes[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(1):47-62.
[3]严洪森[1].新的先进制造模式知识表示方法[J].机械工程学报,2006,42(10):80-90.
[4]薛朝改,严洪森.基于Agent网的知识网的自重构研究[J].计算机集成制造系统,2003,9(11):995-1000.
[5]杨宏兵[1],严洪森[1].知识化制造系统中动态调度的自适应策略研究[J].控制与决策,2007,22(12):1335-1340.
[6]杨宏兵[1],严洪森[1].基于自动机的知识化制造单元死锁控制策略研究[J].中国机械工程,2009,10(5):546-552.
[7]马开平[1,2],严洪森[1].产品市场扩散行为预测的自学习方法[J].计算机集成制造系统,2008,14(12):2484-2491.
[8]薛朝改[1],严洪森[1].基于用户功能需求的知识网的自动生成研究[J].控制与决策,2005,20(9):996-1001.
[9]Garey M R, Johnson D S, Sethi R. The Complexity of Flow- shop and Job- shop Scheduling [J]. Mathematics of Operations Research, 1976, 1 (2): 117-129.
[10]Grabowski J, Wodecki M. A Very Fast Tabu Search Algorithm for the Permutation Flow-shop Problem with Makespan Criterion[J]. Computers and Operations Research, 2004, 31(11): 1891-1909.
[11]Reeves C R, Yamada T. Genetic Algorithms, Path Relinking, and the Flowshop Sequencing Problem[J]. Evolutionary Computation, 1998, 6 (1): 45-60.
[12]Wang L, Zheng D Z. An Effective Hybrid Heuristic for Flow Shop Scheduling[J]. The International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44.
[13]Ogbu F, Smith D. Simulated Annealing for Permutation Flowshop Problem[J]. Omega, 1990, 19 (1) : 64-67.
[14]Anurag A, Selcuk C, Enes E. Improvement Heuristic for the Flow-shop Scheduling Problem: an Adaptive - learning Approach [J]. European of Operational Research, 2006, 169(2): 801-815.
[15]Lee I, Michael J S. A Neural-net Approach to Real Time Flow-shop Sequencing[J]. Computers Industrial Engineering, 2000, 38(1): 125-147.
[16]Aydin M E, Oztemel E. Dynamic Job-shop Scheduling Using Reinforcement Learning Agents[J]. Robotics and Autonomous Systems, 2000, 33(2): 169- 178.
[17]Solimanpur M, Vrat P, Shankar R. A Neural- tabu Search Heuristic for Flow-shop Scheduling Problem[J]. Computers& Operations Research, 2004, 31(11): 2151-2164.
[18]Wang Y C, Usher J M. Application of Reinforcement Learning for Agent- based Production Scheduling[J]. Engineering Applications of Artificial Intelligence, 2005, 18(1): 73-82.
[19]Stefan P. Flow-shop Scheduling Based on Reinforcement Learning Algorithm [ J ]. Production Systems and Information Engineering, 2003, 1 (1) : 83-90.
[20]Haykin S. Neural Networks: a Comprehensive Foundation[M]. 2nd. Beijing: China Machine Press, 2004.
[21]Mitchell T M. Machine Learning[J]. Beijing: China Machine PreSs, 2003.
[22]Taillard E. Benchmarks for Basic Scheduling Problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285.
[23]Cristianini N, Shawe T J. An Introduction to Support Vector Machines and other Kernel- based Learning Methods[M]. Beijing: China Machine Press, 2005.