Approximation Algorithms for Scheduling with Reservations

被引：0
|
作者：
Florian Diedrich
Klaus Jansen
Fanny Pascual
Denis Trystram
机构：
[1] Christian-Albrechts-Universität zu Kiel,Institut für Informatik
[2] Université Pierre et Marie Curie,LIP6
[3] Grenoble University,LIG
来源：
Algorithmica | 2010年 / 58卷
关键词：
Scheduling; Approximation algorithms; Reservations; Approximation scheme; PTAS; Complexity; Inapproximability;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan Cmax, which is the maximum completion time.
引用
收藏
页码：391 / 404
页数：13
相关论文
共 50 条
  • [1] Approximation algorithms for scheduling with reservations
    Diedrich, Florian
    Jansen, Klaus
    Pascual, Fanny
    Trystram, Denis
    HIGH PERFORMANCE COMPUTING - HIPC 2007, PROCEEDINGS, 2007, 4873 : 297 - +
  • [2] Approximation Algorithms for Scheduling with Reservations
    Diedrich, Florian
    Jansen, Klaus
    Pascual, Fanny
    Trystram, Denis
    ALGORITHMICA, 2010, 58 (02) : 391 - 404
  • [3] Approximation algorithms for scheduling problems
    Ishii, H.
    Tada, M.
    IEICE Transactions on Information and Systems, 2000, E83-D (03) : 496 - 502
  • [4] Approximation algorithms for scheduling problems
    Ishii, H
    Tada, M
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2000, E83D (03): : 496 - 502
  • [5] Approximation algorithms for time constrained scheduling
    Jansen, K
    Ohring, S
    INFORMATION AND COMPUTATION, 1997, 132 (02) : 85 - 108
  • [6] APPROXIMATION ALGORITHMS FOR SCHEDULING ON UNIFORM PROCESSORS
    FRACCHIA, FD
    SAXTON, LV
    INFOR, 1993, 31 (01) : 16 - 23
  • [7] Approximation algorithms for layered multicast scheduling
    Cai, QB
    Liberatore, V
    ALGORITHMS AND COMPUTATION, 2005, 3827 : 974 - 983
  • [8] Approximation algorithms for multiprocessor scheduling problem
    Fujita, S
    Yamashita, M
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2000, E83D (03) : 503 - 509
  • [9] Improved approximation algorithms for Broadcast Scheduling
    Bansal, Nikhil
    Coppersmith, Don
    Sviridenko, Maxim
    PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 344 - 353
  • [10] Approximation Algorithms for Average Stretch Scheduling
    Michael A. Bender
    S. Muthukrishnan
    Rajmohan Rajaraman
    Journal of Scheduling, 2004, 7 : 195 - 222
12345