Bi-criteria scheduling problems: number of tardy jobs and maximum weighted tardiness

Bi-criteria scheduling problems: number of tardy jobs and maximum weighted tardiness

0.00 Avg rating0 Votes
Article ID: iaor20084381
Country: Netherlands
Volume: 177
Issue: 1
Start Page Number: 116
End Page Number: 134
Publication Date: Feb 2007
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time pj, a due date dj and a weight wj. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.

Reviews

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