Online non-preemptive scheduling with resource augmentation

According to the resource augmentation model, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this work, we present a framework that unifies the various types of resource augmentation. Our framework is based on mathematical programming and it consists of extending the domain of feasible solutions for the algorithm with respect to the domain of the adversary. This, in turn allows the natural concept of duality for mathematical programming to be used as a tool for the analysis of the algorithm’s performance. As an illustration of the above ideas, we apply this framework and we propose a primal-dual algorithm for the online scheduling problem of minimizing the total weighted flow time of jobs on unrelated machines when the preemption of jobs is not allowed. This is a well representative problem since a strong lower bound exists even for the offline unweighted version of the problem on a single machine. Using the generalized framework for resource augmentation and by combining speed augmentation and rejection, we present and analyze the first constant-factor competitive algorithm for the problem whose ratio depends on the parameters of the augmentation. Finally, inspired by this greedy algorithm, we present an online heuristic for non-preemptive scheduling sequential jobs, which outperforms standard scheduling policies as shown by an extensive campaign of simulations on instances obtained by real traces.