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

Share/Save/Bookmark

Hurink, J.L. (1998) A tabu search approach for a single-machine batching problem using an efficient method to calculate a best neighbour. Journal of Scheduling, 1 (3). pp. 127-148. ISSN 1094-6136

[img] PDF
Restricted to UT campus only
: Request a copy
156kB
Abstract: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.
Item Type:Article
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/63600
Official URL:http://www3.interscience.wiley.com/cgi-bin/abstract/6274/
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page