Scheduling equal processing time jobs to minimize the weighted number of late jobs
type: Item
instance of: scholarly article
title: Scheduling equal processing time jobs to minimize the weighted number of late jobs
zbMATH Open document ID: 1126.90019
author: Svetlana A. Kravchenko
author: Peter Brucker
published in: JMMA. Journal of Mathematical Modelling and Algorithms
publication date: 2006-11-17T00:00:00Z
review text: 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.
reviewed by: Helmut G. Kahlbacher
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5073716
zbMATH Keywords: preemtive
zbMATH Keywords: non-preemptive
zbMATH Keywords: complexity
MaRDI profile type: Publication
full work available at URL: s10852-005-9011-4
OpenAlex ID: W2025422398
cites work: Q4396949
cites work: Open shop problems with unit time operations
cites work: Preemptive job-shop scheduling problems with a fixed number of jobs
cites work: Q4198056
DOI: 10.1007/S10852-005-9011-4
description: scientific article; zbMATH DE number 5073716