Paper Info
Title
Scheduling problem with multi-purpose parallel machines.
Abstract
We consider a multi-purpose identical parallel machine scheduling problem, in which jobs should be executed on some machine belonging to a given subset of the set of machines. The problem is PMPM|r"j;p"j=1|@?w"jU"j, where there are n independent unit-time jobs, time window constraints, m identical parallel multi-purpose machines, and the objective is the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is O(n^2m(n+logm)), employing network flow techniques. We develop an algorithm that handles successive nesting of on-time jobs more efficiently, with O(n^3) overall time complexity.
Year
DOI
Venue
2014
10.1016/j.dam.2011.11.033
Discrete Applied Mathematics
Keywords
Field
DocType
tardy job,m identical parallel multi-purpose,overall time complexity,on-time job,previous complexity,time window constraint,scheduling problem,network flow technique,n independent unit-time job,multi-purpose parallel machine,multi-purpose identical parallel machine,algorithms
Flow network,Discrete mathematics,Combinatorics,Machine scheduling,Multiprocessor scheduling,Job shop scheduling,Computer science,Scheduling theory,Minification,Time complexity
Journal
Volume
ISSN
Citations 
164
0166-218X
1
PageRank 
References 
Authors
0.39
5
3
Name
Order
Citations
PageRank
Rosiane de Freitas Rodrigues1113.14
Mitre Dourado29018.43
Jayme Luiz Szwarcfiter361895.79