ABSTRACT
In all the other case studies (Chapters 11 to 14), we are given full knowledge of a problem instance, and we are interested in finding the best possible solution for that particular instance. In this chapter, however, we are focusing on online problems, i.e., on problems for which algorithmic decisions must be taken before all the characteristics of the whole instance are known. More specifically, we are considering online scheduling problems. Several tasks are submitted to a system that must process them. The scheduling system must decide at what time to allocate which resource to which task. The problem being online by nature, the system does not know beforehand how many tasks it will have to process, when they will arrive in the system, and what their characteristics will be. Hence, the scheduling system will have to make decisions with only a partial knowledge of the instance at hand. One would think that in such a context it is impossible to design optimal algorithms. However, some scheduling problems are still simple enough to enable the existence of algorithms making optimal decisions at any step of any online scenario. For more complex problems, we need a way to assess the quality of the solution produced by an online algorithm, independently of the scenario. This is the purpose of competitive analysis.
