On scheduling around large restrictive common due windows

On scheduling around large restrictive common due windows

0.00 Avg rating0 Votes
Article ID: iaor200688
Country: Netherlands
Volume: 162
Issue: 3
Start Page Number: 740
End Page Number: 761
Publication Date: May 2005
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

This paper deals with the problem of scheduling a number of jobs on a single machine around a large, restrictive common due window. We consider individual earliness and tardiness penalties for the jobs. The objective is to find an optimal schedule which jointly minimizes the sum of the earliness and tardiness penalties. This problem is intractable and hence no efficient procedure for solving large instances is expected to be found. For this reason we first introduced a mapping of the problem which takes advantage of the structural properties inherent to optimal solutions. Secondly we solved the problem under study by using this mapping and applying three meta-heuristics, namely evolutionary strategy, simulated annealing and threshold accepting. To validate the quality of these approaches, altogether 250 benchmark problems with different window sizes and positions of up to 200 jobs are examined. Furthermore small instances are solved to optimality by a mixed integer programming formulation.

Reviews

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