Paper Info
Title
Scheduling on parallel identical machines with job-rejection and position-dependent processing times
Abstract
We solve scheduling problems which combine the option of job-rejection and general position-dependent processing times. The option of rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. The assumption of position-dependent processing time is a common generalization of classical settings, and contains the well-known and extensively studied special cases of ''learning'' and ''aging''. The machine setting is parallel identical machines, and two scheduling measures are considered: total flow-time and total load. When the number of jobs is given, both problems are shown to be solved in polynomial time in the number of jobs. The special case of non-decreasing job-position processing times (''aging'') is shown to be solved much faster.
Year
DOI
Venue
2012
10.1016/j.ipl.2012.06.009
Inf. Process. Lett.
Keywords
Field
DocType
parallel identical machine,position-dependent processing time,general position-dependent processing time,special case,total load,job-position processing time,polynomial time,total flow-time,common scenario,scheduling measure,common generalization,scheduling
Discrete mathematics,Computer science,Scheduling (computing),Arithmetic,Flow time,Time complexity,Distributed computing,Special case
Journal
Volume
Issue
ISSN
112
19
0020-0190
Citations 
PageRank 
References 
10
0.52
13
Authors
2
Name
Order
Citations
PageRank
Enrique Gerstl1637.72
Gur Mosheiov21073105.02