A tabu search algorithm for the job shop problem with sequence dependent setup times |
| |
Affiliation: | 1. Martin-Luther-University Halle-Wittenberg, School of Economics, Halle 06108, Germany;2. 4flow AG, Berlin 10587, Germany |
| |
Abstract: | This paper addresses the classic job shop scheduling problem where sequence dependent setup times are present. Based on a modified disjunctive graph, we further investigate and generalize structural properties for the problem under study. A tabu search algorithm with a sophisticated neighbourhood structure is then developed. Compared to most studies in this research area, we are interested in moving internal critical operations rather than merely focusing on non-internal ones. Moreover, neighbourhood functions are defined using insertion techniques instead of simple swaps. Test results show that our algorithm outperforms a simulated annealing algorithm which is recently published. We have also conducted experiments considering the efficiency of developed propositions. |
| |
Keywords: | Tabu search Scheduling Job shop Set up times |
本文献已被 ScienceDirect 等数据库收录! |
|