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 条
  • [31] Approximation algorithms for batch scheduling with processing set restrictions
    Chai, Xing
    Li, Wenhua
    Ng, C. T.
    Cheng, T. C. E.
    JOURNAL OF SCHEDULING, 2023, 26 (06) : 523 - 533
  • [32] Approximation algorithms for batch scheduling with processing set restrictions
    Xing Chai
    Wenhua Li
    C. T. Ng
    T. C. E. Cheng
    Journal of Scheduling, 2023, 26 : 523 - 533
  • [33] Approximation algorithms for problems in scheduling with set-ups
    Divakaran, Srikrishnan
    Saks, Michael
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (05) : 719 - 729
  • [34] Bicriteria approximation algorithms for scheduling problems with communications delays
    Bampis, E
    Kononov, A
    JOURNAL OF SCHEDULING, 2005, 8 (04) : 281 - 294
  • [35] Different Approximation Algorithms for Channel Scheduling in Wireless Networks
    Ni, Qiufen
    Huang, Chuanhe
    Pardalos, Panos M.
    Ye, Jia
    Fu, Bin
    MOBILE INFORMATION SYSTEMS, 2020, 2020
  • [36] Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times
    Oron, Daniel
    Shabtay, Dvir
    Steiner, George
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 256 (02) : 384 - 391
  • [37] Bicriteria approximation algorithms for scheduling problems with communications delays
    Evripidis Bampis
    Alexander Kononov
    Journal of Scheduling, 2005, 8 : 281 - 294
  • [38] Approximation algorithms for inventory constrained scheduling on a single machine
    Morsy, Ehab
    Pesch, Erwin
    JOURNAL OF SCHEDULING, 2015, 18 (06) : 645 - 653
  • [39] Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability
    Diedrich, Florian
    Jansen, Klaus
    Praedel, Lars
    Schwarz, Ulrich M.
    Svensson, Ola
    ACM TRANSACTIONS ON ALGORITHMS, 2012, 8 (03)
  • [40] Approximation algorithms for shop scheduling problems with minsum objective
    Queyranne, M
    Sviridenko, M
    JOURNAL OF SCHEDULING, 2002, 5 (04) : 287 - 305
12345