Cited By
View all- Hung RTing H(2008)Competitive analysis of most-request-first for scheduling broadcasts with start-up delayTheoretical Computer Science10.1016/j.tcs.2008.01.036396:1-3(200-211)Online publication date: 1-May-2008
Design and analysis of online batching systems
Pages 605 - 616
Abstract
In this paper, we study the design and analysis of online batching systems. In particular, we analyze the tradeoff relationship between the start-up delay and the efficient usage of resources in an online batching system, and analyze how the delay affects the performance of such system. We derive almost optimal upper and lower bounds on the competitive ratio of any deterministic scheduling algorithm for online batching systems. Our results cover in a general way many different batching systems and give interesting insights into the effect of start-up delay.
References
[1]
C.C. Aggarwal, J.L. Wolf, and P.S. Yu. On optimal batching policies for video-ondemand storage servers. In Proceedings of the IEEE International Conference on Multimedia Computing Multimedia Computing and Systems, pages 200-209, 1996.
[2]
M. Azizoglu and S. Webster. Scheduling a batch processing machine with incompatible job families. Computer and Industrial Engineering, 39:325-335, 2001.
[3]
P. Baptiste. Batching identical jobs. Mathematical Methods of Operations Research, 53:355-367, 2000.
[4]
A. Bar-Noy, J.A. Garay, and A. Herzberg. Sharing video on demand. Discrete Applied Mathematics, 129:3-30, 2003.
[5]
A. Bar-Noy, J. Goshi, and R. Ladner. Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging. In Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architecture, pages 164-173, 2003.
[6]
A. Bar-Noy, S. Guha, Y. Katz, J. Naor, B. Schieber, and H. Shachnai. Throughput maximization of real-time scheduling with batching. In Proceedings of the 13th Symposium on Discrete Algorithms, pages 742-751, 2002.
[7]
A. Bar-Noy, R.E. Ladner, and T. Tamir. Scheduling techniques for media-ondemand. In Proceeding of the Annual ACM/SIAM Symposium on Discrete Algorithms, pages 791-800, 2003.
[8]
C. Bouras, V. Kapoulas, G. Pantziou, and P. Spirakis. Competitive video on demand schedulers for popular movies. Discrete Applied Mathematics, 129:49-61, 2002.
[9]
P. Brucker, A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C. Potts, T. Tauthenhahn, and S.L. Van de Velde. Scheduling a batching machine. Journal of Scheduling, 1:31-54, 1998.
[10]
A. Dan, D. Sitaram, and P. Shahabuddin. Dynamic batching policies for an ondemand video server. ACM Multimedia Systems Journal, 4(3):112-121, 1996.
[11]
J. Edmonds and K. Pruhs. Multicast pull scheduling: when fairness is fine. Algorithmica, 2003.
[12]
L. Engebretsen and M. Sudan. Harmonic broadcasting is optimal. In Proceeding of the Annual ACM/SIAM Symposium on Discrete Algorithms, pages 431-432, 2002.
[13]
W. Evans and D. Kirkpatrick. Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. In Proceeding of the Annual ACM/SIAM Symposium on Discrete Algorithms, pages 1041-1049, 2004.
[14]
M. Goldwasser. Patience is a virtue: The effect of slack on competitiveness for admission control. In Proceedings of the 10th Annual Symposium on Discrete Algorithms, pages pp. 396-405, 1999.
[15]
B. Kalyanasundaram and M. Velauthapillai. On-demand broadcasting under deadline. In Proceedings of the 11th Annual European Symposium on Algorithms, volume 2832 of Lecture Notes in Computer Science, pages 313-324, 2003.
[16]
J.H. Kim and K.Y. Chwa. Scheduling broadcasts with deadlines. In Proceedings of the 9th Annual International Conference on Computing and Combinatorics, volume 2697 of Lecture Notes in Computer Science, pages 415-424, 2003.
[17]
S.V. Mehta and R. Uzsoy. Minimizing total tardiness on a batch processing machine with incompatible jobs types. IIE Transactions, 32:165-175, 1998.
Recommendations
Design and Analysis of Online Batching Systems
In this paper, we study the design and analysis of online batching systems, which can be used to model many popular IT systems such as the Video-On-Demand system and the Pull-based Data Dissemination system. We analyze how the start-up delay affects the ...
GRASP with Variable Neighborhood Descent for the online order batching problem
AbstractThe Online Order Batching Problem (OOBP) is a variant of the well-known Order Batching Problem (OBP). As in the OBP, the goal of this problem is to collect all the orders that arrive at a warehouse, following an order batching picking policy, ...
A heuristic approach for the online order batching problem with multiple pickers
AbstractThe Online Order Batching Problem with Multiple Pickers (OOBPMP) consists of optimizing the operations related to the picking process of orders in a warehouse, when the picking policy follows an order batching strategy. In this case, ...
Highlights- Literature review of the Online Order Batching Problem with multiple pickers (OOBPMP).
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- CONICYT: CONICYT via grant Anillo en Redes
- CLEI: Centro Latinoamericano de Estudios en Informática
- CMM, U. Chile: Centro de Modelamiento Matemático (CMM), U. Chile
- IFIP: International Federation for Information Processing
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 20 March 2006
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025
Other Metrics
Citations
Cited By
View all- Hung RTing H(2008)Competitive analysis of most-request-first for scheduling broadcasts with start-up delayTheoretical Computer Science10.1016/j.tcs.2008.01.036396:1-3(200-211)Online publication date: 1-May-2008