This dissertation, "Scheduling Online Batching Systems" by Yee-shing, Regant, Hung, 洪宜成, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled Scheduling Online Batching Systems Submitted by Hung Yee Shing Regant for the Degree of Master of Philosophy at The University of Hong Kong in August 2005 Scheduling batching systems has been studied extensively in the Operations Re- search Community because many traditional production processes such as burn-in process in VLSI manufacturing and di(R)usion process in semiconductor fabrication can be modeled as batching systems. In a batching system, there are some batch- ing servers. Each server can process more than one job simultaneously. Jobs are classied into families. Only the jobs of the same family can form a batch. Jobs in a batch share a server and start and complete at the same time. We guarantee a startup delay in batching systems. A job is either rejected or served by the system within the startup delay after the arrival of the job (i.e. if a job arrives at time t, it will be served at or before t+d where d denotes startup delay). In this thesis, we studyonlinebatchingsystemsthatariseinmanyITapplicationssuchason-demand data broadcasting and video-on-demand systems. We perform a comprehensive study on scheduling online batching systems. We rst look into how the performance of the batching system is a(R)ected by the length of the startup delay. On one hand, we derive lower bounds on the competitive ratio in terms of the startup delay. On the other hand, we design and analyze a greedy algorithm that is based on Most Requested First heuristic. We give an analysis that reveals the exact competitive ratio of our algorithm in terms of the startup delay. An analysis of the performance of the algorithm and the lower bounds on the competitive ratio provide insights into how to design a cost-e(R)ective batching system.We also study the e(R)ect of extra resources on the performance of batching sys- tems. Weobtaintwoformulasshowingthetradeo(R)relationshipbetweenthenumber of servers and startup delay for maintaining some xed level of performance of the systems. System performance is not only a(R)ected by the number of servers and startup delay, but also by the number of families in the batching system. We give a lower boundonthecompetitiveratiointermsofthenumberoffamilies. Thislowerbound reveals that the the greater the number of families, the larger the lower bound is. Based on this lower bound, we design an ecient online algorithm that performs e(R)ectively when there are not many families. Finally, we study the model of video-on-demand systems, a typical example of batching systems. Recently, many researchers have designed online algorithms that adapt to the number of client requests in order to save bandwidth. These algorithms assume that clients must have plenty of bu(R)er to store a portion of the movie. However, thebu(R)ersizeofsmallportabledevicesisusuallysmall. Inviewof advances in technology that enable some small portable devices such as 3G mobile phones to access movies, we design an online algorithm that can simultaneously adapt to the number of requests and adapt to heterogeneous clients in the sense of di(R)erent bu(R)er size. DOI: 10.5353/th_b3462401 Subjects: Production scheduling - Data processing Multimedia systems Algorithms