Combinatorial algorithms for scheduling jobs to minimize server usage time

This thesis is concerned with three combinatorial optimization problems for job scheduling, named the MinUsageTime Dynamic Bin Packing problem, the Energy-Efficient Job Scheduling problem and the Flexible Job Scheduling problem. These problems are motivated by emerging issues arising from cloud computing and energy-efficient computing. A central theme of these problems is to minimize the server usage time for processing jobs. In this thesis, we focus on the algorithmic aspects of each problem by proposing online and approximation algorithms in the online and offline settings respectively. The MinUsageTime Dynamic Bin Packing problem aims at packing a set of items arriving and departing over time to minimize the accumulated bin usage time. We study the problem in three different settings. In the offline setting, the information of all the items to pack is assumed known, whereas in the online setting, the items must be placed into bins as they arrive without any knowledge of future item arrivals. The online setting can be further divided into non-clairvoyant and clairvoyant cases. In the non-clairvoyant case, the departure time of each item is not known at the time of its arrival and cannot be used for packing purposes. In the clairvoyant case, the departure time of each item is known for packing purposes. In this thesis, we first show that the First Fit packing algorithm achieves a competitive ratio of µ + 3 in the non-clairvoyant online setting, where µ is the max/min item duration ratio. This competitive ratio closely matches a known lower bound µ on the competitiveness of any deterministic online algorithm and shows that First Fit packing is near optimal. In the clairvoyant online setting, we establish a lower bound of Ω (log µ / log log µ)^1/2 on the competitive ratio of any deterministic online algorithm. We also propose a classify-by-duration strategy, which can be applied in First Fit packing to achieve a competitive ratio of O(log µ). In the offline setting, we propose two O(1)-approximation algorithms, including a 5-approximation Duration Descending First Fit algorithm and a 4-approximation Dual Coloring algorithm. The Energy-Efficient Job Scheduling problem aims at scheduling a set of jobs to minimize the energy consumption of the machines used. We assume the following energy model. When a machine is “on”, its power usage rate is given by a base rate representing the power consumed by an idle machine plus a variable rate that is proportional to the machine’s instantaneous load. When a machine is “off”, it does not consume energy. State transitions between “on” and “off” incur energy overheads. We show that this Energy-Efficient Job Scheduling problem is a generalization of the MinUsageTime Dynamic Bin Packing problem. In a special case where each job has a unit size equal to the machine capacity, we propose an optimal offline algorithm and an optimal 2-competitive online algorithm. For the general case where jobs can have arbitrary sizes, we first establish a non-trivial lower bound on the optimal solution. Based on this lower bound, we develop a 5-approximation algorithm in the offline setting. In the non-clairvoyant online setting, we design a Modified First Fit algorithm which is O(µ)-competitive, where µ is the max/min job processing length ratio. We show that the Modified First Fit strategy can be adopted to further construct an O(√log µ)-competitive algorithm in the clairvoyant online setting which is asymptotically tight. The Flexible Job Scheduling problem aims at determining the starting times of flexible jobs that do not have to be started immediately at their arrivals to minimize the span of all the jobs, where the span is the time duration in which at least one job is running. In the non-clairvoyant online setting, we first show that no deterministic online scheduler can achieve a competitive ratio less than µ. Then, we propose two O(µ)- competitive schedulers: Batch and Batch+. The Batch+ scheduler is proved to have a tight competitive ratio of µ + 1. In the clairvoyant online setting, we establish a lower bound of 2 on the competitive ratio of any deterministic online scheduler, and propose two O(1)-competitive schedulers: Classify-by-Duration Batch+ and Profit. The Profit scheduler can achieve a competitive ratio of 4 + 2√ 2. These results can be used to extend the MinUsageTime Dynamic Bin Packing problem to model jobs that have laxity in starting.Doctor of Philosoph