Efficient neighborhood search for the one-machine earliness–tardiness scheduling problem

Efficient neighborhood search for the one-machine earliness–tardiness scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20083739
Country: Netherlands
Volume: 173
Issue: 1
Start Page Number: 108
End Page Number: 119
Publication Date: Aug 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

This paper addresses the one-machine scheduling problem where the objective is to minimize a sum of costs such as earliness–tardiness costs. Since the sequencing problem is NP-hard, local search is very useful for finding good solutions. Unlike scheduling problems with regular cost functions, the scheduling (or timing) problem is not trivial when the sequence is fixed. Therefore, the local search approaches must deal with both job interchanges in the sequence and the timing of the sequenced jobs. We present a new approach that efficiently searches in a large neighborhood and always returns a solution for which the timing is optimal.

Reviews

Required fields are marked *. Your email address will not be published.