A tabu search approach for a single-machine batching problem using an efficient method to calculate a best neighbour
✍ Scribed by Johann Hurink
- Publisher
- Springer US
- Year
- 1998
- Tongue
- English
- Weight
- 153 KB
- Volume
- 1
- Category
- Article
- ISSN
- 1094-6136
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we present a tabu search approach for a single-machine batching problem. A set of jobs has to be scheduled on a batching machine. This machine is able to handle several jobs simultaneously. The time for processing a subset of jobs simultaneously is equal to the sum of the processing times of the jobs in the subset plus a set-up time. The goal is to ÿnd a solution which minimizes the sum of weighted completion times. Since for a ÿxed sequence of jobs an e cient method for calculating the best partition of this sequence into batches is known, local search may be applied by considering sequences as solutions. We show that the problem of ÿnding the best sequence in the adjacent pair interchange neighbourhood can be speeded up by considering the calculation of the objective values of all neighboured sequences simultaneously. Computational results show that using the e cient calculation of the best neighbour, the adjacent pair interchange neighbourhood slightly outperforms a shift neighbourhood and in combination with the shift neighbourhood leads to a very e cient tabu search approach.