Scheduling of tasks with effectiveness precedence constraints

被引：0
作者：
Emily A. Heath
John E. Mitchell
Thomas C. Sharkey
机构：
[1] The MITRE Corporation,Department of Mathematical Sciences
[2] Rensselaer Polytechnic Institute,Deparment of Industrial and Systems Engineering
[3] Rensselaer Polytechnic Institute,undefined
来源：
Optimization Letters | 2020年 / 14卷
关键词：
Scheduling; Effectivness precedence constraints; Single machine scheduling; Total weighted completion time;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We formally present the problem of scheduling tasks with effectiveness precedence relationships in order to achieve the minimum total weighted completion time. We provide the problem formulation and define the scope of the problem considered. We present computational complexity results for this problem and an approximation algorithm for it. We prove the theoretical performance of our algorithm and demonstrate its efficiency and practical performance through computational testing, which includes a comparison to the optimal results obtained with an integer programming formulation.
引用
收藏
页码：37 / 49
页数：12
相关论文
共 43 条
[11]  
Lawler E(2004)Scheduling with AND/OR precedence constraints SIAM J. Comput. 33 393-415
[12]  
Lenstra J(1994)Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times Int. J. Prod. Res. 32 1243-1263
[13]  
Kan AR(2016)Identification and classification of restoration interdependencies in the wake of Hurricane Sandy J. Infrastruct. Syst. 22 1-12
[14]  
Hall L(1956)Various optimizers for single stage production Nav. Res. Logist. 3 59-66
[15]  
Schulz A(1999)A polyhedral approach to single-machine scheduling problems Math. Program. 85 541-572
[16]  
Shmoys D(2002)The relation of time indexed formulations of single machine scheduling problems to the node packing problem Math. Programm. 93 477-494
[17]  
Wein J(undefined)undefined undefined undefined undefined-undefined
[18]  
Jaskowski P(undefined)undefined undefined undefined undefined-undefined
[19]  
Sobotka A(undefined)undefined undefined undefined undefined-undefined
[20]  
Johannes B(undefined)undefined undefined undefined undefined-undefined
12345