13 - Scheduling to Minimize Flow Time (Delay)

Summary

Introduction

In this chapter, we begin our discussion on the problem of scheduling jobs with multiple servers, which has widespread applications in areas of operations research, communication networks, etc. Essentially, jobs with a certain processing requirement, called size, arrive over time. There are multiple identical fixed-speed servers, and the problem is to assign jobs to fixed-speed servers so as to minimize some function of the job response time (departure minus the arrival time).

Different objectives are of interest for solving the scheduling problem that are application specific. For example, when an application depends on the time when all the jobs are finished, then makespan (the finishing time of the last completed job) is considered, while when the total delay is of interest, flow time (sum of the response times of all jobs) is the chosen objective. A special case of flow time is the completion time, which is defined as the sum of the departure times of all jobs, disregarding their arrival times.

As we discussed in Chapter 12, the load balancing problem with the objective of minimizing the maximum load is the same as minimizing makespan. Thus, in this chapter, we concentrate on solving the scheduling problem with the objective of minimizing the flow time. The completion time problem is simpler than the flow time problem.

For the considered scheduling problem, multiple classes of restrictions are possible, e.g., whether preemption is allowed or not, can a job be migrated between servers or not, are jobs required to be assigned to a server (which cannot be changed later) as soon as they arrive or not, whether server speeds are identical or not, and, finally, is there a job–server assignment restriction (a job can be processed by only a subset of servers). Different restrictions imply very different results on the competitive ratio for online algorithms.

In this chapter, we concentrate on the simplest setting where both preemption and job migration are allowed. Moreover, we consider that all servers are identical, having fixed speed, with no job–server assignment restriction, and a job can be assigned to a server any time after it has arrived, and not necessarily on its arrival. Some other settings are explored via problems at the end of the chapter. Scheduling problem with variable speed servers is discussed in the next chapter.