Solving the serial batching problem in job shop manufacturing systems

This paper addresses the serial batch scheduling problem embedded in a job shop environment to minimize makespan. Sequence dependent family setup times and a job availability assumption are also taken into account. In consideration of batching decisions, we propose a tabu search algorithm which consists of various neighborhood functions, multiple tabu lists and a sophisticated diversification structure. Computational experiments show that our algorithm outperforms a well-known tabu search approach which is developed for solving the traditional job shop problem. These results also confirm the benefits of batching.

► This study is strongly motivated by practical applications. ► Very limited publications addressing job shop serial batching problems are currently available. ► The proposed algorithm outperforms a metaheuristic for standard job shop problems. ► Computational results confirm the significant benefits of batching.