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

帅旗; 姚锡凡

doi:10.3969/j.issn.0258-2724.2012.03.025

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

doi: 10.3969/j.issn.0258-2724.2012.03.025

帅旗^1,2,
姚锡凡^1, ,

基金项目:

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

详细信息

作者简介:
帅旗(1974-),男,讲师,硕士,研究方向为数控和机械制造,E-mail:jimmyscnshuai@163.com

通讯作者:
姚锡凡(1964-),男,教授,博士,研究方向为数控和自动控制,E-mail:mexfyao@scut.edu.cn

计量
- 文章访问数: 1378
- HTML全文浏览量: 57
- PDF下载量: 453
- 被引次数: 0
出版历程
- 收稿日期: 2011-06-02
- 刊出日期: 2012-06-25

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

SHUAI Qi^1,2,
YAO Xifan^{1
, ,}

摘要

摘要: 为克服传统进化算法求解较大型柔性作业调度问题计算时间长和结果不稳定的缺点,提出了一种启发性规则求解方法.该方法用一个启发性规则产生初始调度解,再利用一些启发式规则对初始调度过程中的关键工件及关键工序进行搜索,并对关键路径进行优化调整得到较优解,通过比较得到柔性调度问题的优化调度解.用本文方法对典型柔性调度问题进行求解,并与其他算法的求解结果进行比较,对于1510问题,采用本文方法的计算结果与混合基因算法相同,计算时间为3.2 s,减少了42%;对于2310及2510的较大型问题,表明启发性规则的引入能提高求解效率,与传统进化算法相比,更适合求解较复杂的柔性作业调度问题.
- 柔性作业调度问题 /
- 启发式规则 /
- 关键路径
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 1510 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 2310 and 2510 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.
- flexible job-shop scheduling problem /
- heuristic rule /
- critical path

HTML全文

参考文献(16)

BRUKER P, SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4): 369-375.

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.

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.

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.

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.

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.

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.

孟祥伟,张平,李春锦. 到场飞机排序及调度问题的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.

白俊杰,龚毅光,王宁生,等. 多目标柔性作业车间分批优化调度[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.

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.

周支立,李怀祖.单抓钩动态排序的启发式算法[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.

崔健双,李铁克. 一种求解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.

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.

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.

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.

吴秀丽, 李苏剑, 杜彦华. 柔性作业车间多品种小批量调度算法研究[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.

施引文献

附加材料(0)

访问统计