TY - JOUR
T1 - 'Strong''weak' precedence in scheduling
T2 - Extensions to seriesparallel orders
AU - Dror, Moshe
AU - Steiner, George
N1 - Funding Information:
This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under grant No. OG1798-08 .
PY - 2010/8/28
Y1 - 2010/8/28
N2 - We examine computational complexity implications for scheduling problems with job precedence relations with respect to strong precedence versus weak precedence. We propose a consistent definition of strong precedence for chains, trees, and seriesparallel orders. Using modular decomposition for partially ordered sets (posets), we restate and extend past complexity results for chains and trees as summarized in Dror (1997) [5]. Moreover, for seriesparallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems.
AB - We examine computational complexity implications for scheduling problems with job precedence relations with respect to strong precedence versus weak precedence. We propose a consistent definition of strong precedence for chains, trees, and seriesparallel orders. Using modular decomposition for partially ordered sets (posets), we restate and extend past complexity results for chains and trees as summarized in Dror (1997) [5]. Moreover, for seriesparallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems.
KW - Posets
KW - Scheduling
KW - Strong and weak precedence
UR - http://www.scopus.com/inward/record.url?scp=77956177097&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77956177097&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2010.06.015
DO - 10.1016/j.dam.2010.06.015
M3 - Article
AN - SCOPUS:77956177097
VL - 158
SP - 1767
EP - 1776
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
IS - 16
ER -