Combinatorial algorithms for scheduling jobs to minimize server usage time
Runtian Ren · 2018
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 µ ) 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.i