Randomized online scheduling with delivery times

被引:7
|
作者
Seiden, S [1 ]
机构
[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
关键词
analysis of algorithms; online algorithms; scheduling;
D O I
10.1023/A:1009875403874
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is phi approximate to 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.
引用
收藏
页码:399 / 416
页数:18
相关论文
共 50 条
  • [31] Supply chain scheduling with deteriorating jobs and delivery times
    Mao, Rong-Rong
    Lv, Dan-Yang
    Ren, Na
    Wang, Ji-Bo
    JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2024, 70 (03) : 2285 - 2312
  • [32] Research on delivery times scheduling with truncated learning effects
    Ren, Na
    Wang, Ji-Bo
    Wang, Ershen
    COMPUTATIONAL & APPLIED MATHEMATICS, 2023, 42 (06):
  • [33] Improved Randomized Online Scheduling of Intervals and Jobs
    Fung, Stanley P. Y.
    Poon, Chung Keung
    Zheng, Feifeng
    THEORY OF COMPUTING SYSTEMS, 2014, 55 (01) : 202 - 228
  • [34] Randomized online scheduling on two uniform machines
    Epstein, L
    Noga, J
    Seiden, S
    Sgall, J
    Woeginger, G
    PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1999, : 317 - 326
  • [35] Online interval scheduling: randomized and multiprocessor cases
    Stanley P. Y. Fung
    Chung Keung Poon
    Feifeng Zheng
    Journal of Combinatorial Optimization, 2008, 16 : 248 - 262
  • [36] Online interval scheduling: randomized and multiprocessor cases
    Fung, Stanley P. Y.
    Poon, Chung Keung
    Zheng, Feifeng
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2008, 16 (03) : 248 - 262
  • [37] Online interval scheduling: Randomized and multiprocessor cases
    Fung, Stanley P. Y.
    Poon, Chung Keung
    Zheng, Feifeng
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2007, 4598 : 176 - +
  • [38] PREEMPTIVE SCHEDULING WITH RELEASE DATES, DELIVERY TIMES AND SEQUENCE INDEPENDENT SETUP TIMES
    ZDRZALKA, S
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 76 (01) : 60 - 71
  • [39] Improved Randomized Online Scheduling of Intervals and Jobs
    Stanley P. Y. Fung
    Chung Keung Poon
    Feifeng Zheng
    Theory of Computing Systems, 2014, 55 : 202 - 228
  • [40] A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times
    Badri, Hossein
    Bahreini, Tayebeh
    Grosu, Daniel
    COMPUTERS & OPERATIONS RESEARCH, 2021, 130