A tabu search approach for a single-machine batching problem using an efficient method to calculate a best neighbour

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 find a solution which minimizes the sum of weighted completion times. Since for a fixed sequence of jobs an efficient 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 finding 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 efficient 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 efficient tabu search approach.