Robust Scheduling Algorithms

Abstract

In the classic online scheduling model, jobs arrive one after another. At the arrival of a new job, the scheduler must immediately and irrevocably assign it to a machine. In the parallel machine case, we have m identical machines to process the jobs. Each job j has a processing time p j that is revealed at the moment of its appearance. The load of a machine is the sum of processing times of jobs assigned to it. The objective is to minimize the makespan, that is, the maximum machine load.The fact that decisions are irrevocable imposes a hard constraint on the scheduler. However, many applications allow some amount of flexibility. Robust scheduling algorithms take this flexibility into account: whenever a job arrives, some reassignment of jobs can be performed. More precisely, given a parameter β > 0, the arrival of job j allows to migrate a set of jobs with a total processing time of at most β ⋅p j . The factor β is called the migration factor of the algorithm and it is a measure of its robustness. In this context, the quality of solutions is assessed by competitive analysis: an algorithm is α-competitive if for any sequence of job arrivals the makespan of the algorithm is at most α times the (offline) optimum cost for the set of available jobs. An important goal in this area is to understand the trade-off between the migration and competitive factors.