The Complexity of Parallel Machine Scheduling of Unit-Processing-Time Jobs under Level-Order Precedence Constraints

被引：3
作者：
Wang, Tianyu [1 ]
Bellenguez-Morineau, Odile [1 ]
机构：
[1] Inst Mines Telecom Atlantique, LS2N, CNRS, UMR 6004, 4 Rue Alfred Kastler,BP 20722, F-44307 Nantes 3, France
来源：
JOURNAL OF SCHEDULING | 2019年 / 22卷 / 03期
关键词：
Parallel machine scheduling; Level-order; Precedence constraints;
D O I：
10.1007/s10951-018-0596-7
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
In this paper, we prove that parallel machine scheduling problems where jobs have unit processing time and level-order precedence constraints are NP-complete, while minimizing the makespan or the total completion time. These problems are NP-complete even when preemption is allowed. We then adapt the proof to other open problems with out-tree or opposing-forests precedence constraints.
引用
收藏
页码：263 / 269
页数：7
相关论文
共 12 条
[1]   On preemption redundancy in scheduling unit processing time jobs on two parallel machines [J].
Baptiste, P ;
Timkovsky, VG .
OPERATIONS RESEARCH LETTERS, 2001, 28 (05) :205-212
[2]   How useful are preemptive schedules? [J].
Brucker, P ;
Heitmann, S ;
Hurink, J .
OPERATIONS RESEARCH LETTERS, 2003, 31 (02) :129-136
[3]  
Brucker P., 1977, Mathematics of Operations Research, V2, P275, DOI 10.1287/moor.2.3.275
[4]   PROFILE SCHEDULING OF OPPOSING FORESTS AND LEVEL ORDERS [J].
DOLEV, D ;
WARMUTH, MK .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (04) :665-687
[5]  
Garey M.-R., 2002, COMPUTERS INTRACTABI
[6]   SCHEDULING OPPOSING FORESTS [J].
GAREY, MR ;
JOHNSON, DS ;
TARJAN, RE ;
YANNAKAKIS, M .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (01) :72-93
[7]  
Graham R. L., 1979, Discrete Optimisation, P287
[8]   PARALLEL SEQUENCING AND ASSEMBLY LINE PROBLEMS [J].
HU, TC .
OPERATIONS RESEARCH, 1961, 9 (06) :841-848
[9]  
Pinedo ML, 2012, SCHEDULING: THEORY, ALGORITHMS, AND SYSTEMS, FOURTH EDITION, P1
[10]   A survey on how the structure of precedence constraints may change the complexity class of scheduling problems [J].
Prot, D. ;
Bellenguez-Morineau, O. .
JOURNAL OF SCHEDULING, 2018, 21 (01) :3-16
12