Online time constrained scheduling with penalties
Nicolas Rudolph Thibault, Christian Laforest · 2009
In this paper we prove the (constant) competitiveness of an online algorithm for scheduling jobs on multiple machines, supporting a mechanism of penalties for the scheduler/operator. Our context (online, multiple machines, supporting parameterizable penalties) is more general than in previous existing works. The main contribution of our paper is the (non trivial) analysis of our algorithm. Moreover, with our parameterizable penalties, the operator can find a trade-off between the attractiveness of its system and its own profit (gained with non canceled scheduled jobs).