On the on-line maintenance scheduling problem

被引:2
作者
Shamsaei, Fahimeh [1 ]
Telha, Claudio [1 ]
Van Vyve, Mathieu [1 ]
机构
[1] Catholic Univ Louvain, Ctr Operat Res & Econometr, Voie Roman Pays 34, B-1348 Louvain La Neuve, Belgium
关键词
Maintenance scheduling; Competitive analysis; Randomized algorithms;
D O I
10.1007/s11590-017-1198-6
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
A machine instantly serves requests but needs to undergo maintenance after serving a maximum of L requests. We want to maximize the number of requests served. In the on-line version, we prove that serving L requests before placing a maintenance is 0.5-competitive and is best possible for deterministic algorithms. We describe a 0.585-competitive randomized algorithm and show an upper bound of . We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.
引用
收藏
页码:387 / 397
页数:11
相关论文
共 14 条
[1]   Better bounds for online scheduling [J].
Albers, S .
SIAM JOURNAL ON COMPUTING, 1999, 29 (02) :459-473
[2]  
[Anonymous], 1997, Introduction to linear optimization
[3]  
[Anonymous], 2009, Lectures on stochastic programming: modeling and theory
[4]  
Ascheuer N., 1999, OP RES P 1998, P21
[5]  
Babaioff M, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P434
[6]   Toward Robust Revenue Management: Competitive Analysis of Online Booking [J].
Ball, Michael O. ;
Queyranne, Maurice .
OPERATIONS RESEARCH, 2009, 57 (04) :950-963
[7]   Robust optimization - methodology and applications [J].
Ben-Tal, A ;
Nemirovski, A .
MATHEMATICAL PROGRAMMING, 2002, 92 (03) :453-480
[8]   Approximation techniques for average completion time scheduling [J].
Chekuri, C ;
Motwani, R ;
Natarajan, B ;
Stein, C .
SIAM JOURNAL ON COMPUTING, 2001, 31 (01) :146-166
[9]   Online Stochastic Matching: Beating 1-1/e [J].
Feldman, Jon ;
Mehta, Aranyak ;
Mirrokni, Vahab ;
Muthukrishnan, S. .
2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :117-126
[10]   On the competitive ratio for Online Facility Location [J].
Fotakis, Dimitris .
ALGORITHMICA, 2008, 50 (01) :1-57