|
|
论文:2016,Vol:34,Issue(4):635-641 |
|
|
引用本文： |
|
|
李兢尧, 黄媛, 王军强, 郭阳明. 求解扩展双资源约束作业车间调度的分支种群遗传算法[J]. 西北工业大学学报 |
|
|
Li Jingyao, Huang Yuan, Wang Junqiang, Guo Yangming. Branch Population Genetic Algorithm for Extension Dual Resource Constrained Job Shop Scheduling Problem[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 求解扩展双资源约束作业车间调度的分支种群遗传算法 |
|
| 李兢尧1, 黄媛2, 王军强3, 郭阳明4 |
|
1. 西北工业大学 第365研究所, 陕西 西安 710065;
2. 西北工业大学 机电学院, 陕西 西安 710072;
3. 西北工业大学 系统集成与工程管理研究所, 陕西 西安 710072;
4. 西北工业大学 计算机学院, 陕西 西安 710072 |
| 摘要: |
| 根据扩展双资源约束作业车间调度问题的特点，构造了一种混合遗传算法进行求解:以分支种群为载体继承遗传进化经验，利用精英进化算子、基于扇形分割的轮盘赌选择算子及邻域搜索等机制，进一步优化了算法性能。通过分析策略对比仿真、算法性能对比仿真等实验，结果表明上述各种优化机制可行，且对于算法运算效率与寻优性能的优化效果均有良好表现。 |
| 关键词:
调度算法
扩展双资源约束
作业车间调度
分支种群
精英进化
扇形分割
邻域搜索
|
|
| Branch Population Genetic Algorithm for Extension Dual Resource Constrained Job Shop Scheduling Problem |
|
| Li Jingyao1, Huang Yuan2, Wang Junqiang3, Guo Yangming4 |
|
1. Research Institute of 365,Northwestern Polytechnical University, Xi'an 710065, China;
2. School of Mechanical Engineering, Northwestern Polytechnical University, Xi'an 710072, China;
3. Institute of System Integrated and Engineering Management, Northwestern Polytechnical University, Xi'an 710072, China;
4. School of Computer, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| In this paper, a hybrid genetic algorithm was proposed for solving extension dual resource constrained job shop scheduling problem. The algorithm was constructed based on inheriting evolution experience of parent population with the branch population. In addition, this algorithm used some optimization operators to optimize algorithm performance, such as the elite evolutionary operator, the roulette selection operator based on sector partition, the variable neighbourhood search operator, and so on. Finally, the optimization performances of above mechanisms were validated according to the statistical analysis on the simulation results of strategies comparison simulation and algorithm performance comparison simulation. |
| Key words:
scheduling algorithm
extension dual resource constrained
job shop scheduling
branch population
elite evolutionary
sector partition
neighborhood search
|
|
| 收稿日期: 2015-10-12
修回日期:
|
| DOI: |
| 基金项目: 国家自然科学基金（51275421）和西北工业大学基础研究基金（JC20120227）资助 |
| 通讯作者:
Email： |
| 作者简介: 李兢尧(1984-),西北工业大学讲师,主要从事智能算法及调度优化研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Elmaraghy H, Patel V, Abdallah I B. Scheduling of Manufacturing Systems under Dual-Resource Constraints Using Genetic Algorithms[J]. Journal of Manufacturing Systems, 2000, 19(3): 186-201
[2] 周炳海, 蒋舒宇, 何平, 等. 基于双重资源的柔性生产系统调度算法[J]. 华南理工大学学报, 2008, 36(4): 45-49 Zhou Binghai, Jiang Shuyu, He Ping, et al. Scheduling Algorithm of Flexible Production System Based on Dual Resource[J]. Journal of South China University of Technology, 2008, 36(4): 45-49 (in Chinese)
[3] 陶泽, 隋天中, 谢里阳,等. 基于Petri网和GASA的双资源JSP动态优化调度[J]. 东北大学学报, 2007, 28(3): 405-409 Tao Ze, Sui Tianzhong, Xie Liyang, et al. Dynamic Scheduling Optimization of Dual-Resource Based on Petri Net and GASA[J]. Journal of Northeastern University, 2007, 28(3): 405-409 (in Chinese)
[4] 陈勇, 吴云翔, 王亚良. 订单不确定下双资源约束多装配线鲁棒调度[J]. 中国机械工程, 2014, 25(12): 1567-1573 Chen Yong, Wu Yunxiang, Wang Yaliang. Multi-Assembly Line Robust Scheduling of Double Resource Constrains under Uncertain Orders[J]. China Mechanical Engineering, 2014, 25(12): 1567-1573 (in Chinese)
[5] Araza U, Salum L. A Multi-Criteria Adaptive Control Scheme Based on Neural Networks and Fuzzy Inference for DRC Manufacturing Systems[J]. International Journal of Production Research, 2010, 48(1): 251-270
[6] 李兢尧,孙树栋,黄媛,等. 双资源约束作业车间调度算法研究[J]. 机械工程学报, 2010, 46(22): 175-181 Li Jingyao, Sun Shudong, Huang Yuan, et al. Algorithm for Dual Resource Constrained Job Shop Scheduling[J]. Journal of Mechanical Engineering, 2010, 46(22): 175-181 (in Chinese)
[7] 李兢尧,孙树栋,黄媛,等. 求解双资源约束车间调度问题的继承式双目标遗传算法[J]. 控制与决策, 2011, 26(12): 1761-1767 Li Jingyao, Sun Shudong, Huang Yuan, et al. Double Objective Inherited Genetic Algorithm for Dual Resource Constrained Job Shop[J]. Control and Decision, 2011, 26(12): 1761-1767 (in Chinese)
[8] 李兢尧,孙树栋,黄媛,等. 基于时窗的双资源约束车间调度研究[J]. 机械工程学报, 2011, 46(22): 150-159 Li Jingyao, Sun Shudong, Huang Yuan, et al. Research on Dual Resource Constrained Job Shop Scheduling Based on Time Window[J]. Journal of Mechanical Engineering, 2011, 46(22): 150-159 (in Chinese)
[9] 李兢尧,孙树栋,黄媛,等. 基于自适应参数混合蚁群算法的双资源约束作业车间调度[J]. 西北工业大学学报, 2011, 29(1): 54-61 Li Jingyao, Sun Shudong, Huang Yuan, et al. Solving Dual Resource Constrained Job-Shop Scheduling Problem(DRCJSP) Based on Hybrid Ant Colony Algorithm with Self-Adaptive Parameters[J]. Journal of Northwestern Polytechnical University, 2011, 29(1): 54-61 (in Chinese)
[10] 张超勇, 饶运清, 李培根. 柔性作业车间调度问题的两级遗传算法[J]. 机械工程学报, 2007, 43(4): 119-124 Zhang Chaoyong, Rao Yunqing, Li Peigen. Bilevel Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Chinese Journal of Mechanical Engineering, 2007, 43(4): 119-124 (in Chinese)
[11] Jingyao L, Shudong S, Yuan H. Dual Resource Constrained Job Shop Scheduling Based on Time Window[J]. Chinese Journal of Mechanical Engineering, 2011, 47(16): 150-159
[12] 潘全科, 王文宏, 朱剑英. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统, 2007, 13(2): 323-329 Pan Quanke, Wang Wenhong, Zhu Jianying. Hybrid Heuristics Based on Particle Swarm Optimization and Variable Neighborhood Search for Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2007, 13(2): 323-329 (in Chinese)
[13] Chu C, Proth J M, Wang C. Improving Job Shop Schedules Through Critical Pairwise Exchanges[J]. International Journal of Production Research, 1998, 36(3): 683-694
[14] Nowicki E, Smutnicki C. A Fast Taboo Search Algorithm for the Job Shop Scheduling[J]. Management Science, 1996, 42(6): 797-813
[15] Doerner K, Gutjahr W, Hartl R, et al. Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection[J]. Annals of Operations Research, 2004, 131(1): 79-99
[16] 张勇德, 黄莎白. 多目标优化问题的蚁群算法研究[J]. 控制与决策, 2005, 20(2): 170-176 Zhang Yongde, Huang Shabai. On Ant Colony Algorithm for Solving Multiobjective Optimization Problems[J]. Control And Decision, 2005, 20(2): 170-176 (in Chinese) |
|
|
|
|
|
|
|
