SEK Improves

When a service system has multiple servers and a single queue of jobs, deciding which job to process when a server becomes available is essential to minimizing response time. This decision is called a scheduling problem. The simplest scheduling policy is First-Come-First-Serve (FCFS), but it is well-known that this is not optimal. In the last couple of years, the celebrated Shortest-Remaining-Processing-Time (SRPT) has been proved to be optimal in mean response time and tail behavior. Indeed, SRPT is the best policy identified in the literature. In this work, we propose the SEK policy and prove that it performs better than SRPT. In particular, when one job is in the queue (not being served), we can reorganize the jobs so that the longest job gets service in one server and the second longest is scheduled right after the shortest job. With this simple reorganization of jobs, we show that the response time and number of processed jobs are better under SEK than SRPT.