Minmax earliness–tardiness costs with unit processing time jobs

Minmax earliness–tardiness costs with unit processing time jobs

0.00 Avg rating0 Votes
Article ID: iaor20013915
Country: Netherlands
Volume: 130
Issue: 3
Start Page Number: 638
End Page Number: 652
Publication Date: May 2001
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.

Reviews

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