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

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

CLC Number:

F 406

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.

References

［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]	LIU Yahui, SHEN Xingwang, GU Xinghai, PENG Tao, BAO Jinsong, ZHANG Dan. A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1262-1275.
[2]	LI Dechang, YANG Hualong, DUAN Jingru. A Joint Optimization of Vessel Scheduling and Refueling Strategy for Container Liner Shipping with Cooperative Agreements [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 953-964.
[3]	LI Linyan, HAN Shuang, QIAO Yanhui, LI Li, LIU Yongqian, YAN Jie, LIU Haidong. A Wind-Solar-Electric Vehicles Coordination Scheduling Method for High Proportion New Energy Grid-Connected Scenarios [J]. Journal of Shanghai Jiao Tong University, 2022, 56(5): 554-563.
[4]	WANG Zixiang, WU Zerui, LIU Ran. Weekly Physician Scheduling for Emergency Departments with Time-Varying Demands of Patients with Revisits [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 242-252.
[5]	TANG Hongtao, WANG Dannan, SHAO Yiping, ZHAO Wenbin, JIANG Weiguang, CHEN Qingfeng. A Modified Migrating Birds Optimization for Multi-Objective Lot Streaming Hybrid Flowshop Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.
[6]	LU Qiuyu, YU Zhen, YANG Yinguo, LI Li. Two-Stage Optimal Schedule of Offshore Wind-Power-Integrated Multi-Microgrid Considering Uncertain Power of Sources and Loads [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1308-1316.
[7]	WANG Jinfeng, CHEN Lu, YANG Wenhui. A Single Machine Scheduling Problem Considering Machine Availability Constraints [J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 103-110.
[8]	JIANG Xiaokang, ZHANG Peng, LÜ Youlong, ZHAO Xinming, ZHANG Jie. Hybrid Ant Colony Algorithm for Batch Scheduling in Semiconductor Furnace Operation [J]. Journal of Shanghai Jiaotong University, 2020, 54(8): 792-804.
[9]	LI Baihe, JIANG Zuhua, TAO Ningrong, MENG Lingtong, ZHENG Hong. Ship Block Transportation Scheduling Considering Cooperative Transportation of Flatcars [J]. Journal of Shanghai Jiaotong University, 2020, 54(7): 718-727.
[10]	ZHU Hongwei, LU Zhiqiang. Modeling and Optimization of Resource Constrained Project Scheduling Problem Considering Employee-Timetabling [J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 624-635.
[11]	MENG Lingtong, JIANG Zuhua, TAO Ningrong, LIU Jianfeng, ZHENG Hong. Multi-Stockyard Scheduling Considering Technological Process and Combined Assembly Block [J]. Journal of Shanghai Jiao Tong University, 2020, 54(4): 331-343.
[12]	MA Changpu，ZHOU Binghai. Scheduling of Multi-Load Rail Guided Vehicles in AS/RS with Collision Avoidance Constrains [J]. Journal of Shanghai Jiaotong University, 2020, 54(2): 126-134.
[13]	FANG Jia, LU Zhiqiang. Modeling and Optimization of Robust Scheduling Template Considering Equipment Failure [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1278-1290.
[14]	ZHAO Rui, GU Xingsheng. A Discrete Sine Optimization Algorithm for No-Idle Flow-Shop Scheduling Problem [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1291-1299.
[15]	CUI Weiwei (崔维伟). Approximate Approach to Deal with the Uncertainty in Integrated Production Scheduling and Maintenance Planning [J]. Journal of Shanghai Jiao Tong University (Science), 2020, 25(1): 106-117.