APPROXIMATION ALGORITHMS FOR SCHEDULING ON UNIFORM PROCESSORS

被引:0
|
作者
FRACCHIA, FD
SAXTON, LV
机构
关键词
ALGORITHM ANALYSIS; APPROXIMATION ALGORITHMS; SCHEDULING; UNIFORM PROCESSES;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-polynomial time algorithm is very unlikely unless P = NP. This paper deals with approximation schemes which attempt to find a solution in polynomial time that is close to the optimal solution. Specifically, two variants of LPT scheduling are shown: one which is polynomial time and the other a probabilistically good algorithm.
引用
收藏
页码:16 / 23
页数:8
相关论文
共 50 条
  • [1] Approximation Algorithms for Scheduling with Reservations
    Diedrich, Florian
    Jansen, Klaus
    Pascual, Fanny
    Trystram, Denis
    ALGORITHMICA, 2010, 58 (02) : 391 - 404
  • [2] Approximation Algorithms for Scheduling with Reservations
    Florian Diedrich
    Klaus Jansen
    Fanny Pascual
    Denis Trystram
    Algorithmica, 2010, 58 : 391 - 404
  • [3] Fast approximation algorithms for uniform machine scheduling with processing set restrictions
    Leung, Joseph Y-T.
    Ng, C. T.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 260 (02) : 507 - 513
  • [4] APPROXIMATION ALGORITHMS FOR SCHEDULING PARALLEL JOBS
    Jansen, Klaus
    Thoele, Ralf
    SIAM JOURNAL ON COMPUTING, 2010, 39 (08) : 3571 - 3615
  • [5] Scheduling chains on uniform processors with communication delays
    Kubiak, W
    Penz, B
    Trystram, D
    JOURNAL OF SCHEDULING, 2002, 5 (06) : 459 - 476
  • [6] Efficient approximation algorithms for scheduling moldable tasks
    Wu, Xiaohu
    Loiseau, Patrick
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 310 (01) : 71 - 83
  • [7] IMPROVED APPROXIMATION ALGORITHMS FOR SHOP SCHEDULING PROBLEMS
    SHMOYS, DB
    STEIN, C
    WEIN, J
    SIAM JOURNAL ON COMPUTING, 1994, 23 (03) : 617 - 632
  • [8] Multi-organization scheduling approximation algorithms
    Cohen, Johanne
    Cordeiro, Daniel
    Trystram, Denis
    Wagner, Frederic
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2011, 23 (17): : 2220 - 2234
  • [9] Approximation Algorithms for Average Stretch Scheduling
    Michael A. Bender
    S. Muthukrishnan
    Rajmohan Rajaraman
    Journal of Scheduling, 2004, 7 : 195 - 222
  • [10] Approximation Algorithms for Multitasking Scheduling Problems
    Zheng, Feifeng
    Wang, Zhaojie
    Liu, Ming
    Chu, Chengbin
    IEEE ACCESS, 2020, 8 (127530-127534): : 127530 - 127534