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 条
[1]  
Anderson E(2004)On-line scheduling of a single machine to minimize total weighted completion time Math. Oper. Res. 29 686-697
[2]  
Potts C(2005)Single-machine scheduling with precedence constraints Math. Oper. Res. 30 1005-1021
[3]  
Correa J(2002)Comparing an aco algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times J. Oper. Res. Soc. 53 895-906
[4]  
Schulz A(1995)Scheduling tasks with AND/OR precedence constraints SIAM J. Comput. 24 797-810
[5]  
Gagné C(1979)Optimization and approximation in deterministic sequencing and scheduling: a survey Ann. Discrete Math. 5 287-326
[6]  
Price W(1997)Scheduling to minimize average completion time: off-line and on-line approximation algorithms Math. Oper. Res. 22 513-544
[7]  
Gravel M(2012)Using soft precedence relations for reduction of the construction project duration Technol. Econ. Dev. Econ. 18 262-279
[8]  
Gillies D(2005)On the complexity of scheduling unit-time jobs with OR-precedence constraints Oper. Res. Lett. 33 587-596
[9]  
Liu J(2008)Single-machine scheduling problems with past-sequence-dependent setup times Eur. J. Oper. Res. 187 1045-1049
[10]  
Graham R(2004)On-line scheduling to minimize average completion time revisited Oper. Res. Lett. 32 485-490
12345