Scheduling equal processing time jobs to minimize the weighted number of late jobs
| Autor(en): | Brucker, P. Kravchenko, S.A. |
Stichwörter: | Jobs with equal processing times; NP-hardness; Parallel machine scheduling; Polynomial algorithm; Preemption | Erscheinungsdatum: | 2006 | Enthalten in: | Journal of Mathematical Modelling and Algorithms | Band: | 5 | Ausgabe: | 2 | Startseite: | 143 | Seitenende: | 165 | Zusammenfassung: | We prove that the problem P | p i = p, pmtn |∑w iUi 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. © Springer 2006. |
ISSN: | 15701166 | DOI: | 10.1007/s10852-005-9011-4 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33646896732&doi=10.1007%2fs10852-005-9011-4&partnerID=40&md5=917ee2bb7550d3685d2939916fa0cac4 |
Zur Langanzeige
