Paper Info
Title
Scheduling on parallel identical machines with late work criterion: Offline and online cases
Abstract
Abstract In the paper, we consider the problem of scheduling jobs on parallel identical machines with the late work criterion and a common due date, both offline and online cases. Since the late work criterion has not been studied in the online mode so far, the analysis of the online problem is preceded by the analysis of the offline problem, whose complexity status has not been formally stated in the literature yet. Namely, for the offline mode, we prove that the two-machine problem is binary NP-hard, and the general case is unary NP-hard. In the online mode we assume that jobs arrive in the system one by one, i.e., we consider the online over list model. We give an algorithm with a competitive ratio being a function of the number of machines, and we prove the optimality of this approach for two identical machines.
Year
DOI
Venue
2016
10.1007/s10951-015-0464-7
Journal of Scheduling
Keywords
Field
DocType
Online and offline scheduling,Identical parallel machines,Late work,NP-hardness,Competitive ratio
Mathematical optimization,Unary operation,Computer science,Scheduling (computing),Real-time computing,Binary number,Competitive analysis
Journal
Volume
Issue
ISSN
19
6
1099-1425
Citations 
PageRank 
References 
4
0.43
26
Authors
4
Name
Order
Citations
PageRank
Chen Xin1625120.92
Małgorzata Sterna21049.18
Xin Han321324.49
Jacek Blazewicz41064154.23