A recovering beam search algorithm for the single machine Just-in-Time scheduling problem

A recovering beam search algorithm for the single machine Just-in-Time scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20083737
Country: Netherlands
Volume: 172
Issue: 3
Start Page Number: 798
End Page Number: 813
Publication Date: Aug 2006
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: heuristics, programming: multiple criteria
Abstract:

We consider the Just-in-Time scheduling problem where the Just-in-Time notion is captured by means of multiple conflicting criteria. The calculation of any non-dominated solution for these criteria is achieved by solving an extension of the single machine problem of minimising the mean weighted deviation from distinct due dates. In the extended problem each job to schedule is also constrained by a release date and a deadline. This problem is NP-Hard in the strong sense and we propose heuristic algorithms to solve it. Computational experiments show that, among those algorithms, the most effective heuristic, in terms of quality, is a Recovering Beam Search algorithm.

Reviews

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