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]	YANG Yinguo, FENG Yinying, WEI Wei, XIE Pingping, CHEN Yue. Coordinated Day-Ahead Scheduling and Real-Time Dispatch of a Wind-Thermal-Storage Energy Base Considering Flexibility Interval [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1270-1280.
[2]	ZHANG Li, WANG Bao, JIA Jianxiong, SONG Zhumeng, YE Yutong, YU Yue, LIN Jiaqing, XU Xiaoyuan. End-to-End Collaborative Optimization Method for Microgrid Power Prediction and Optimal Scheduling [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 720-731.
[3]	CHEN Shi, YANG Linsen, LIU Yihong, LUO Huan, ZANG Tianlei, ZHOU Buxiang. Optimal Scheduling Strategy of Newly-Built Microgrid in Small Sample Data-Driven Mode [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 732-745.
[4]	ZHONG Ming, WU Ying, WU Chunli, WANG Fang. Tugboat Scheduling Problem Considering Time Windows and Flexible Returning Way to Base [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(6): 1276-1288.
[5]	ZHAO Yingying, QIU Yue, ZHU Tianchen, LI Fan, SU Yun, TAI Zhenying, SUN Qingyun, FAN Hang. Online Steady-State Scheduling of New Power Systems Based on Hierarchical Reinforcement Learning [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 400-412.
[6]	QIU Zizhang, WANG Dawang, LU Zhifeng, WU Guohua. An Illuminator Resource Scheduling Methods Based on Tabu Search [J]. Air & Space Defense, 2025, 8(3): 132-140.
[7]	HU Kaiqiang, CAI Zexiang, CAI Yu, QU Jing, LIU Yuanyuan. Micro-Service Scheduling Model and Optimization for Protection and Control of Distribution Network Considering Virtualization Delay [J]. Journal of Shanghai Jiao Tong University, 2025, 59(11): 1684-1693.
[8]	ZHANG Jianhua, YAO Yi, ZHAO Si, WANG Yongyue. A Coordinated Control Scheme for Fast Frequency Regulation of Thermal Power Units Based on Flexibility Transformation [J]. Journal of Shanghai Jiao Tong University, 2025, 59(11): 1694-1706.
[9]	WANG Xuan, WANG Bao, CHEN Yanping, LIU Hong, MA Xiaohui. Joint Economic Optimization of AGV Logistics Scheduling and Orderly Charging in a Low-Carbon Automated Terminal [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1370-1380.
[10]	ZHOU Siyi, YANG Huanhong, HUANG Wentao, ZHOU Ze, JIAO Wei, YANG Zhenyu. Two-Stage Day-Ahead and Intra-Day Rolling Optimization Scheduling of Container Integrated Port Energy System [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1357-1369.
[11]	JIANG Zuhua^1∗(蒋祖华), ZHOU Hongming²(周宏明), TAO Ningrong³(陶宁蓉), LI Baihe¹(李柏鹤). Knowledge-Based Curved Block Construction Scheduling and Application in Shipbuilding [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(5): 759-765.
[12]	CHEN Yini(陈旖旎), JIANG Zuhua^* (蒋祖华). Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 492-508.
[13]	GU Huijie, ZHOU Huafeng, PENG Chaoyi, HU Yaping, ZHAO Xinyi, XIE Jun, SHI Xionghua. A Multi-Time Scale Scheduling Model for Power Generation Systems with a High Proportion of New Energy Including Pumped Storage Power Stations [J]. Journal of Shanghai Jiao Tong University, 2024, 58(12): 1957-1967.
[14]	YE Zhiliang, LI Canbing, ZHANG Yongjun, LI Licheng, XIAO Yinjing, WU Yuhang, TAI Nengling. Optimization of Day-Ahead Dispatch Time Resolution in Power System with a High Proportion of Climate-Sensitive Renewable Energy Sources [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 781-790.
[15]	LI Junshuang, HU Yan, TAI Nengling. Collaborative Optimization Scheduling of 5G Base Station Energy Storage and Distribution Network Considering Communication Load and Power Supply Reliability [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 791-802.