Paper Info
Title
A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints
Abstract
We provide a general scheme for constructing monotone algorithms for a wide class $\mathcal{C}$ of scheduling problems Q|prec,r j |γ on related machines with precedence constraints and/or release dates. Our scheme works in the offline and the online setting. It takes as input two approximation/competitive algorithms for the (simpler) scheduling problems P|prec,r j |γ on identical machines and 1|prec,r j |γ on a single machine and then generically constructs a monotone approximation/ competitive algorithm for the problem on related machines. Monotone algorithms are necessary and sufficient for the design of truthful scheduling mechanisms in the setting with selfish machines. The algorithms constructed by our scheme are among the first monotone algorithms for scheduling problems with precedence constraints. For example, we show that our scheme applies to the problems of minimizing the makespan or the weighted sum of completion times when the jobs have precedence constraints and/or release dates.
Year
DOI
Venue
2008
10.1007/978-3-540-93980-1_9
WAOA
Keywords
DocType
Volume
problems p,problems q,general scheme,release date,scheme work,scheduling problems,precedence constraint,related machine,competitive algorithm,monotone algorithm,designing monotone algorithms,precedence constraints,monotone approximation,scheduling problem,algorithmic mechanism design
Conference
5426
ISSN
Citations 
PageRank 
0302-9743
1
0.36
References 
Authors
13
2
Name
Order
Citations
PageRank
Clemens Thielen17515.11
Sven O. Krumke230836.62