西南交通大学学报 2012, 47(3) 509-515 DOI:   10.3969/j.issn.0258-2724.2012.03.025  ISSN: 0258-2724 CN: 51-1277/U

本期目录 | 下期目录 | 过刊浏览 | 高级检索                                                            [打印本页]   [关闭]
论文
扩展功能
本文信息
Supporting info
PDF(0KB)
[HTML全文]
参考文献
服务与反馈
把本文推荐给朋友
加入我的书架
加入引用管理器
引用本文
Email Alert
文章反馈
浏览反馈信息
本文关键词相关文章
柔性作业调度问题
启发式规则
关键路径
本文作者相关文章
帅旗
PubMed
Article by Shuai,q

基于启发性规则及关键路径调整的柔性作业调度优化算法

帅旗1,2, 姚锡凡1

1. 华南理工大学机械工程与汽车学院, 广东 广州 510640;
2. 广东省科学技术职业学院, 广东 珠海 519090

摘要

为克服传统进化算法求解较大型柔性作业调度问题计算时间长和结果不稳定的缺点,提出了一种启发性规则求解方法.该方法用一个启发性规则产生初始调度解,再利用一些启发式规则对初始调度过程中的关键工件及关键工序进行搜索,并对关键路径进行优化调整得到较优解,通过比较得到柔性调度问题的优化调度解.用本文方法对典型柔性调度问题进行求解,并与其他算法的求解结果进行比较,对于15×10问题,采用本文方法的计算结果与混合基因算法相同,计算时间为3.2 s,减少了42%;对于23×10及25×10的较大型问题,表明启发性规则的引入能提高求解效率,与传统进化算法相比,更适合求解较复杂的柔性作业调度问题.

关键词 柔性作业调度问题   启发式规则   关键路径  

Optimization Algorithm for Flexible Job-Shop Scheduling Problem Based on Heuristic Rules and Adjustment of Critical Paths

SHUAI Qi1,2, YAO Xifan1

1. School of Mechanical and Automotive Engineering, South China University of Technology, Guangzhou 510640, China;
2. Guangdong Institute of Science and Technology, Zhuhai 519090, China

Abstract:

In order to overcome the disadvantages of long computing time and unstable result of traditional evolutionary algorithms in solving the optimization for large flexible job-shop problems (FJSPs), a heuristic critical path approach (HCPA) was proposed. This method first uses a heuristic rule to get some preliminary schedules. Then, critical workpieces and key process of these preliminary schedules are searched and critical paths are locally adjusted using some heuristic rules for better solutions. Finally, the optimal schedule of FJSP is obtained by comparison among these solutions. The proposed approach was applied to benchmark FJSPs, and the solutions were compared with those of other approaches. The results show that for the 15×10 FJSP, the values of evaluation indexes computed by the proposed method are nearly the same as those by the integrated genetic algorithm, but the computing time (only 3.2 s) is reduced by 42%. The large FJSPs of 23×10 and 25×10 are also calculated, reflecting that introduction of heuristic rules can improve the computing efficiency and solution stability; compared with the traditional evolutionary algorithms, the proposed method is more suitable for real-time solution of difficult FJSPs.

Keywords: flexible job-shop scheduling problem   heuristic rule   critical path  
收稿日期 2011-06-02 修回日期  网络版发布日期 2012-05-29 
DOI: 10.3969/j.issn.0258-2724.2012.03.025
基金项目:

国家863计划资助项目(2007AA04Z111)

通讯作者: 姚锡凡(1964-),男,教授,博士,研究方向为数控和自动控制,E-mail:mexfyao@scut.edu.cn
作者简介: 帅旗(1974-),男,讲师,硕士,研究方向为数控和机械制造,E-mail:jimmyscnshuai@163.com

参考文献:

[1] BRUKER P, SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4): 369-375.
[2] ZHANG G H, SHAO X Y. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J]. Computers and Industrial Engineering, 2008(7): 1-10.
[3] JIA Z H, CHEN H P, TANG J. An improved particle swarm optimization for multi-objective flexible job-shop scheduling problem//2007 IEEE International Conference on Grey System and intelligent Services. Nanjing: IEEE, 2007: 1587-1592.
[4] CHAO Y Z, XIAO J Z, LIANG G. An improved genetic algorithm for multi-objective flexible job-shop scheduling problem[J]. Advanced Materials Research, 2010, 97: 2449-2454.
[5] SHENG T H, CHIU S Y, YEN S J. An improved multi-objective genetic algorithm for solving flexible job shop problem//2010 IET International Conference on Frontier Computing Theory, Technologies and Applications. Taichung: IET, 2010: 427-431.
[6] JU Q Y, ZHU J Y. Multi-objective flexible job shop scheduling of batch production[J]. Chinese Journal of Mechanical Engineering, 2007, 43(8): 148-154.
[7] AZARDOOST E B, IMANIPOUR N. A hybrid algorithm for multi-objective flexible job shop scheduling problem//Proceedings of the 2011 International Conference on Industrial Engineering and Operations Management. Kuala Lumpur: IEOM, 2011: 795-801.
[8] 孟祥伟,张平,李春锦. 到场飞机排序及调度问题的Memetic算法[J]. 西南交通大学学报,2011,46(3): 488-493. MENG Xiangwei, ZHANG Ping, LI Chunjin. Memetic Algorithm for aircraft arrival sequencing and scheduling problem[J]. Journal of Southwest Jiaotong University, 2011, 46(3): 488-493.
[9] 白俊杰,龚毅光,王宁生,等. 多目标柔性作业车间分批优化调度[J]. 计算机集成制造系统, 2010,16(2): 397-403. BAI Junjie, GONG Yiguang, WANG Ningsheng, et al. Multi-objective flexible job shop scheduling with lot-splitting[J]. Computer Integrated Manufacturing Systems, 2010, 16(2): 397-403.
[10] BOZEJKO W, UCHRONSKI M, WODECKI M. The new golf neighborhood for the flexible job shop problem[J]. Procedia Computer Science, 2010, 1(1): 289-296.
[11] 周支立,李怀祖.单抓钩动态排序的启发式算法[J]. 系统工程理论方法应用,2002,11(2): 136-140. ZHOU Zhili, LI Huaizu. A heuristic method for one hoist dynamic scheduling[J]. Systems Engineering: Theory Methodology Applications, 2002, 11(2): 136-140.
[12] 崔健双,李铁克. 一种求解Job shop 调度问题的启发式组合邻域交换算法[J]. 管理工程学报,2009,23(3): 97-102. CUI Jianshuang, LI Tieke. A heuristic combinatorial neighborhood algorithm for the job shop scheduling problem[J]. Journal of Industrial Engineering Management, 2009, 23(3): 97-102.
[13] KACEM I, HAMMADI S, BORNE P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 2002, 32(1): 1-13.
[14] KACEM I, HAMMADI S, BORNE P. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic[J]. Mathematics and Computers in Simulation, 2002, 60: 245-276.
[15] XIA W J, WU Z M. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J]. Computers and Industrial Engineering, 2005, 48(2): 409-425.
[16] 吴秀丽, 李苏剑, 杜彦华. 柔性作业车间多品种小批量调度算法研究[J]. 中国机械工程,2010,21(4):425-429. WU Xiuli, LI Sujian, DU Yanhua. Research on batch scheduling problem in a flexible job shop[J]. China Mechanical Engineering, 2010, 21(4): 425-429.

本刊中的类似文章
1.周国华; 武振业.求解Flow Shop 排序问题的模拟进化法[J]. 西南交通大学学报, 1997,32(6): 672-676

文章评论 (请注意:本站实行文责自负, 请不要发表与学术无关的内容!评论内容不代表本站观点.)

Copyright 2008 by 西南交通大学学报