Scheduling equal processing time jobs to minimize the weighted number of late jobs

Scheduling equal processing time jobs to minimize the weighted number of late jobs

0.00 Avg rating—0 Votes
Article ID: iaor2007670
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 143
End Page Number: 165
Publication Date: Jun 2006
Journal: Journal of Mathematical Modelling and Algorithms
Authors: ,
Abstract:

We prove that the problem {P|pi=p (all i), pmtn | ∑iwiUi} is unary NP-hard although the corresponding nonpreemptive problem can be solved in O(n log n) time, where n is the number of jobs. This contrasts the fact that usually preemptive problems are not harder than their nonpreemptive counterparts.

Reviews

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