Competitive Analysis of Online Cloud Scheduling with Fare Classes

Online cloud scheduling is becoming a key factor in today's market due to the ubiquity of cloud computing. From the cloud providers' point of view, many online algorithms have been created to decide which customers' requests to accept or reject, in order to maximize profits. However, these solutions give performance guarantees based on strict assumptions, such as the input coming from a probability distribution, or by having the customer wait for a decision. A different setting that employs online algorithms to serve similar purposes is the airline industry, and some of its work ensures a certain level of performance without any assumptions or system parameter knowledge. This thesis addresses online cloud scheduling issues using techniques and models from the airline industry. In particular, it divides the incoming requests into fare classes and applies a Nested Protection Level policy to make acceptance decisions. Theoretical results provide bounds on the resulting competitive ratio.