A multiple-pass heuristic rule for job shop scheduling with due dates

A multiple-pass heuristic rule for job shop scheduling with due dates

0.00 Avg rating0 Votes
Article ID: iaor1994969
Country: United Kingdom
Volume: 31
Issue: 11
Start Page Number: 2677
End Page Number: 2692
Publication Date: Nov 1993
Journal: International Journal of Production Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper presents an efficient multiple-pass heuristic algorithm for job shop scheduling problems with due dates wherein the objective is to minimize total job tardiness. Algorithm operation is carried out in two phases. In phase 1 a dispatching rule is employed to generate an active or non-delay initial schedule. In phase 2, tasks selected from a predetermined set of promising target operations in the initial schedule are tested to ascertain whether by left-shifting their start times and rearranging some subset of the remaining operations one can reduce total tardiness. Performance evaluation is carried out over a range of shop sizes focusing, first of all, on the quality of the initial schedule produced through five commonly used dispatching rules and, secondly, the schedule improvement achieved with the multiple-pass heuristic. Results indicate that the proposed technique is capable of yielding notable reductions in total tardiness (over initial schedules) for practical size problems and would suggest that the approach presents an efficient scheduling option for this class of complex optimization problems.

Reviews

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