Portal de Periódicos da CAPES

Simple Near-Optimal Scheduling for the M/G/1

2019; Association for Computing Machinery; Volume: 47; Issue: 2 Linguagem: Inglês

10.1145/3374888.3374898

1557-9484

Ziv Scully, Mor Harchol‐Balter, Alan Scheller‐Wolf,

Parallel Computing and Optimization Techniques

We consider the problem of preemptively scheduling jobs to minimize mean response time of an M/G/1 queue. When the scheduler knows each job's size, the shortest remaining processing time (SRPT) policy is optimal. Unfortunately, in many settings we do not have access to each job's size. Instead, we know only the job size distribution. In this setting, the Gittins policy is known to minimize mean response time, but its complex priority structure can be computationally intractable. A much simpler alternative to Gittins is the shortest expected remaining processing time (SERPT) policy. While SERPT is a natural extension of SRPT to unknown job sizes, it is unknown how close SERPT is to optimal.