The power of restarts in online scheduling

点击翻译按钮获取中文摘要

Optimiztion under uncertainty is a widely studied field with many different applications. In online scheduling, we make the assumption that the input jobs arrive one by one (or over time) and need to be assigned to machines without knowledge of the remaining input. The goal is to minimize the competitive ratio, which for cost minimization problems is the highest possible ratio over all inputs between the cost of an algorithm for a given input and the optimal cost for the same input. We are interested in online scheduling problems where jobs arrive over time. This project will focus on several common objective functions, in particular on total completion time, total flow time, throughput and the weighted versions of these functions. We will study how to optimize these objective functions in the practically relevant but very rarely studied model with restarts. In this model, it is possible to interrupt a running job in case a more urgent job arrives (a smaller one, or a heavier one), but in this case the job that was running must be restarted from the beginning: the work done on it is lost. This model is also called preemption with restarts and is different from the more commonly studied preemption with resume model, in which any interrupted job can simply be resumed from the point of interruption.The restarts model is well-motivated, as it is not in all situations possible to interrupt running jobs without losing the work done so far. It is therefore important to understand how much restarts can help to improve the performance of online algorithms for scheduling. Our work will provide better results, and in some cases the first results, for this to a large extent neglected research direction.