基于禁忌搜索的柔性作业车间分批调度

上海交通大学学报（自然版） ›› 2012, Vol. 46 ›› Issue (12): 2003-2008.

基于禁忌搜索的柔性作业车间分批调度

陆汉东，何卫平，周旭，李亚杰

(西北工业大学现代设计与集成制造教育部重点实验室, 西安 710072)

收稿日期:2011-12-26 出版日期:2012-12-29 发布日期:2012-12-29
基金资助:
国防基础科研项目（A2720110011）

An Integrated Tabu Search Algorithm for the Lot Streaming Problem in Flexible Job Shops

LU Han-Dong, HE Wei-Ping, ZHOU Xu, LI Ya-Jie

(The Key Laboratory of Contemporary Design and Integrated Manufacturing Technology of Ministry of Education, Northwestern Polytechnical University, Xi’an 710072, China)

Received:2011-12-26 Online:2012-12-29 Published:2012-12-29

摘要/Abstract

摘要： 针对柔性作业车间的分批调度问题，提出了一种基于禁忌搜索算法的柔性分批调度算法.首先进行批次初始划分；然后利用禁忌搜索算法优化批次加工路线和子批加工顺序；最后在零件子批数不变的前提下，利用批量变化局部搜索进行批量分割的优化，实现了最小化完工时间和机床负荷的调度目标.实例分析结果证明了柔性分批调度算法的可行性、高效性和适用性.

关键词: 调度, 批量分割, 柔性作业车间, 禁忌搜索法

Abstract: To solve the problem of flexible job shop scheduling with lot-splitting, a flexible size lot-splitting scheduling algorithm based on tabu search was presented, which incorporates the predetermination of sublot sizes, the determination of schedules based on tabu search and the variation of sublot sizes, to minimize the makespan and machine workload. Performance of the algorithm was evaluated through simulations, and the results demonstrate the feasibility , efficiency and utility of the algorithm.

Key words: scheduling, lot-splitting, flexible job-shop, tabu search

中图分类号:

F 406

陆汉东, 何卫平, 周旭, 李亚杰. 基于禁忌搜索的柔性作业车间分批调度[J]. 上海交通大学学报（自然版）, 2012, 46(12): 2003-2008.

LU Han-Dong, HE Wei-Ping, ZHOU Xu, LI Ya-Jie. An Integrated Tabu Search Algorithm for the Lot Streaming Problem in Flexible Job Shops[J]. Journal of Shanghai Jiaotong University, 2012, 46(12): 2003-2008.

参考文献

［1］Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible jobshop scheduling problem［J］. Computers & Operations Research, 2008,35(10): 32023212.
［2］潘全科,朱剑英.多工艺路线的批量生产调度优化［J］.机械工程学报,2004,40(4):3639.
PAN Quanke, ZHU Jianying. Optimization method for a jobshop scheduling problem with alternative machines in the batch process ［J］. Chinese Journal of Mechanical Engineering,2004,40(4):3639 .
［3］Low C Y, Hsu C M, Huang K I. Benefits of lot splitting in jobshop scheduling ［J］. International Journal of Advanced Manufacturing Technology, 2004, 24( 9/10): 773780.
［4］Jeong H I, Park J W, Leachman R C. A batch splitting method for a job shop scheduling problem in an MRP environment［J］. International Journal of Production Research, 1999, 37(15): 35833598.
［5］孙志峻,安进,黄卫清.作业车间多工艺路线批量作业计划优化［J］.中国机械工程, 2008,19(2): 183187.
SUN Zhijun, AN Jin , HUANG Weiqing. Lot scheduling with multiple process routes in Job Shop［J］ . China Mechanical Engineering, 2008, 19(2):183187.
［6］白俊杰,龚毅光,王宁生,等.多目标柔性作业车间分批优化调度［J］.计算机集成制造系统,2010,16(2):396403.
BAI Junjie, GONG Yiguang,WANG Ningsheng,et al. Multiobjective flexible Job Shop scheduling with lotsplitting［J］. Computer Integrated Manufacturing Systems,2010,16(2):396403.
［7］王凌.智能优化算法及其应用［M］.北京:清华大学出版社,2001:6375.
［8］LI Junqing, PAN Quanke, LIANG Yunchia. An effective hybrid tabu search algorithm for multiobjective flexible jobshop scheduling problems［J］.Computers & Industrial Engineering, 2010,59(4): 647662.
［9］Parviz Fattahi M. Flexible job shop scheduling with tabu search algorithms［J］. The International Journal of Advanced Manufacturing Technology, 2007,32(5/6):563570.
［10］Buscher U, SHEN Liji. An integrated tabu search algorithm for the lot streaming problem in job shops ［J］. European Journal of Operational Research, 2009,199(2):385399.
［11］Yazdani M, Amiri M, Zandieh M. Flexible jobshop scheduling with parallel variable neighborhood search algorithm［J］. Expert Systems with Applications, 2010,37(1):678687.
［12］苏子林.车间调度问题及其进化算法分析［J］.机械工程学报, 2008,44(8):242247.
SU Zilin. Jobshop scheduling problem and its evolution algorithm analysis［J］. Chinese Journal of Mechanical Engineering， 2008,44(8):242247.
［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, 2002, 32(1): 113.

[1]	刘亚辉, 申兴旺, 顾星海, 彭涛, 鲍劲松, 张丹. 面向柔性作业车间动态调度的双系统强化学习方法[J]. 上海交通大学学报, 2022, 56(9): 1262-1275.
[2]	李林晏, 韩爽, 乔延辉, 李莉, 刘永前, 阎洁, 刘海东. 面向高比例新能源并网场景的风光-电动车协同调度方法[J]. 上海交通大学学报, 2022, 56(5): 554-563.
[3]	汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
[4]	陆秋瑜, 于珍, 杨银国, 李力. 考虑源荷功率不确定性的海上风力发电多微网两阶段优化调度[J]. 上海交通大学学报, 2022, 56(10): 1308-1316.
[5]	王兴志, 翟海保, 严亚勤, 吴庆曦. 基于数字孪生和深度学习的新一代调控系统预调度方法[J]. 上海交通大学学报, 2021, 55(S2): 37-41.
[6]	许凌, 王兴志, 肖林朋. 基于语义特征抓取电网调度事件的检测技术[J]. 上海交通大学学报, 2021, 55(S2): 86-91.
[7]	范厚明, 于佳琪, 马梦知, 蒋晓丹, 慈吉利, 翟志伟. 模糊时间窗下多船型不定期船调度与航速联合优化[J]. 上海交通大学学报, 2021, 55(3): 297-310.
[8]	吕祥梅, 刘天琪, 刘绚, 何川, 南璐, 曾红. 考虑高比例新能源消纳的多能源园区日前低碳经济调度[J]. 上海交通大学学报, 2021, 55(12): 1586-1597.
[9]	王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110.
[10]	蒋小康, 张朋, 吕佑龙, 赵新明, 张洁. 基于混合蚁群算法的半导体生产线炉管区调度方法[J]. 上海交通大学学报, 2020, 54(8): 792-804.
[11]	李柏鹤, 蒋祖华, 陶宁蓉, 孟令通, 郑虹. 考虑平板车合作运输的船舶分段堆场间调度[J]. 上海交通大学学报, 2020, 54(7): 718-727.
[12]	朱宏伟, 陆志强. 考虑人力资源排班的资源受限项目调度问题建模与优化[J]. 上海交通大学学报, 2020, 54(6): 624-635.
[13]	孟令通, 蒋祖华, 陶宁蓉, 刘建峰, 郑虹. 考虑工艺顺序和组合分段的多堆场调度方法[J]. 上海交通大学学报, 2020, 54(4): 331-343.
[14]	许显杨，陈璐. 考虑设备可靠性与能耗的平行机调度[J]. 上海交通大学学报, 2020, 54(3): 247-255.
[15]	马昌谱，周炳海. 自动存取系统多载量轨道小车避碰调度方法[J]. 上海交通大学学报, 2020, 54(2): 126-134.