Single machine scheduling with symmetric earliness and tardiness penalties

Single machine scheduling with symmetric earliness and tardiness penalties

0.00 Avg rating0 Votes
Article ID: iaor20042044
Country: Netherlands
Volume: 144
Issue: 3
Start Page Number: 598
End Page Number: 612
Publication Date: Feb 2003
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time production environment. The scheduling problem is formulated as a 0–1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs.

Reviews

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