New scheduling policy for estimation of stationary performance characteristics in single server queues with inaccurate job size information

The study of size-based and size-oblivious scheduling policies with inaccurate job size information appears nowadays to be an important direction of scientific studies because as recent research results show advantages of size-based policies can be saved even when the job sizes are not perfectly known a priori. This paper is focused on the same topic but touches upon a different question: is it possible to predict such estimates of system's performance characteristics (for example, job's mean sojourn time), that will be close to those which will be observed in practice, if the scheduler is provided only with the inaccurate information about the job size distribution? It is shown here that there are conditions under which the answer to the question is positive. A simple mathematical model (M/G/1 queueing system) of a top level view of a data-intensive execution engine is being proposed. It is shown that, in case of long-tailed service time distribution, a special service policy - Preemptive-Last-Come-First-Served with service time re-generation on arrival instants - allows one to obtain better upper bounds for job's mean sojourn time than those achieved by common work conserving policies. Extensive numerical examples are presented. © ECMS Thorsten Claus, Frank Herrmann, Michael Manitz, Oliver Rose (Editors).