Scheduling equal processing time jobs to minimize the weighted number of late jobs (Q853793)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Scheduling equal processing time jobs to minimize the weighted number of late jobs |
scientific article; zbMATH DE number 5073716
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Scheduling equal processing time jobs to minimize the weighted number of late jobs |
scientific article; zbMATH DE number 5073716 |
Statements
Scheduling equal processing time jobs to minimize the weighted number of late jobs (English)
0 references
17 November 2006
0 references
The problem of scheduling \(n\) jobs with equal processing times on \(m\) parallel machine to minimize the weighted number of late jobs is discussed. Where -- as a surprise -- the preemtive version is proved to be an NP-hard problem using a reduction to the numerical matching with target sums problem (stated in Garey and Johnson (1979)). And the non-preemptive version is of complexity \(O(n\log n)\). Beside these two complexity results, extensions and further open problems are stated.
0 references
preemtive
0 references
non-preemptive
0 references
complexity
0 references
