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 条
  • [21] Approximation Algorithms for Scheduling with a Variable Machine Maintenance
    Luo, Wenchang
    Chen, Lin
    Zhang, Guochuan
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, 2010, 6124 : 209 - +
  • [22] Approximation Algorithms for Scheduling with Resource and Precedence Constraints
    Demirci, Gokalp
    Hoffmann, Henry
    Kim, David H. K.
    35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96
  • [23] Improved Approximation Algorithms for Routing Shop Scheduling
    Yu, Wei
    Zhang, Guochuan
    ALGORITHMS AND COMPUTATION, 2011, 7074 : 30 - 39
  • [24] Approximation algorithms for the twin robot scheduling problem
    Florian Jaehn
    Andreas Wiehl
    Journal of Scheduling, 2020, 23 : 117 - 133
  • [25] Approximation algorithms for the twin robot scheduling problem
    Jaehn, Florian
    Wiehl, Andreas
    JOURNAL OF SCHEDULING, 2020, 23 (01) : 117 - 133
  • [26] Approximation Algorithms for Multiprocessor Scheduling under Uncertainty
    Lin, Guolong
    Rajaraman, Rajmohan
    THEORY OF COMPUTING SYSTEMS, 2010, 47 (04) : 856 - 877
  • [27] Approximation algorithms for the multiprocessor scheduling with submodular penalties
    Liu, Xiaofei
    Li, Weidong
    OPTIMIZATION LETTERS, 2021, 15 (06) : 2165 - 2180
  • [28] On the optimality of exact and approximation algorithms for scheduling problems
    Chen, Lin
    Jansen, Klaus
    Zhang, Guochuan
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 96 : 1 - 32
  • [29] Approximation Algorithms for Drone Delivery Scheduling Problem
    Jana, Saswata
    Mandal, Partha Sarathi
    NETWORKED SYSTEMS, NETYS 2023, 2023, 14067 : 125 - 140
  • [30] Efficient approximation algorithms for scheduling moldable tasks
    Wu, Xiaohu
    Loiseau, Patrick
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 310 (01) : 71 - 83
12345