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 条
  • [41] Approximation algorithms for scheduling jobs with chain precedence constraints
    Jansen, K
    Solis-Oba, R
    PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2004, 3019 : 105 - 112
  • [42] Exact and Approximation Algorithms of Scheduling in Evacuation and Recovery Service
    Tang, Huajun
    Levner, Eugene
    2013 INTERNATIONAL CONFERENCE ON ENGINEERING, MANAGEMENT SCIENCE AND INNOVATION (ICEMSI 2013), 2013,
  • [43] Approximation algorithms for inventory constrained scheduling on a single machine
    Ehab Morsy
    Erwin Pesch
    Journal of Scheduling, 2015, 18 : 645 - 653
  • [44] Approximation algorithms for mixed batch scheduling on parallel machines
    Wang, Dong
    Fang, Kan
    Luo, Wenchang
    Ouyang, Wenli
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2024, 75 (12) : 2365 - 2374
  • [45] Approximation algorithms for parallel machine scheduling with linear deterioration
    Liu, Ming
    Zheng, Feifeng
    Wang, Shijin
    Xu, Yinfeng
    THEORETICAL COMPUTER SCIENCE, 2013, 497 : 108 - 111
  • [46] Approximation algorithms for the multiprocessor open shop scheduling problem
    Schuurman, P
    Woeginger, GJ
    OPERATIONS RESEARCH LETTERS, 1999, 24 (04) : 157 - 163
  • [47] Approximation algorithms for scheduling trees with general communication delays
    Munier, A
    PARALLEL COMPUTING, 1999, 25 (01) : 41 - 48
  • [48] Teaching Complex Scheduling Algorithms
    Hunold, Sascha
    Przybylski, Bartlomiej
    2021 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW), 2021, : 321 - 327
  • [49] Optimal and Approximation Algorithms for Joint Routing and Scheduling in Millimeter-Wave Cellular Networks
    Yuan, Dingwen
    Lin, Hsuan-Yin
    Widmer, Jorg
    Hollick, Matthias
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2020, 28 (05) : 2188 - 2202
  • [50] Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms
    Fangfang Wu
    Zhongyi Jiang
    Run Zhang
    Xiandong Zhang
    Journal of Scheduling, 2023, 26 : 383 - 398
12345