Introduction to Scheduling

One of my favourite courses I have taken so far at the University of Waterloo is Scheduling (CO 454).  The course had interesting and applicable material, a great prof, and did not require a lot of background knowledge.  This post will be a crash course on scheduling!  This introduction will not assume any background knowledge in optimization or scheduling, but it will use some basic discrete math and mathematical notation.  If you hate math, stop reading now!


The study of scheduling is exactly what it sounds like.  Given a set of jobs that need to be completed, you want to create a schedule for those jobs that optimizes an objective function.

An example of a scheduling problem is your homework assignments.   You have four assignments due next week, and they all have different due dates.  You might want to create a schedule for you to complete all assignments as soon as possible.  Or it could be that you want to finish the more important assignments first, and work on the less important assignments if you have time.  The order in which you tackle your assignments will depend on what you are optimizing for.

A General Scheduling Problem

A general scheduling problem consists of three items: jobs, machines, and an objective function.

A job j can have various attributes.  It may have some (or all) of the following properties:

 p_j : processing time

{\large d_j} : deadline

{\Large r_j} : release time (the job can’t be processed before this)

w_j: weight (importance of this job relative to other jobs)

… and more

The machines process the jobs.  There may be one or several machines, and each machine may not be identical.  (i.e. machine A might be twice as fast as processing jobs as machine B).  We will only be dealing with one machine in this post.

The objective function is the mathematical function we are trying to optimize.

Feasible Schedules

With the above definitions for a specific scheduling problem, we can create feasible schedules.  For example, let’s say we have one machine, and three jobs, with processing times 1, 2, and 3.  Then this is a Gantt chart of one feasible schedule:

Screenshot 2015-01-01 18.33.08

Let us make the assumption that we will not have unnecessary pre-emption.  This means that a machine will never be idle (free) if there are any jobs available to process.  With this assumption, there are only finitely many feasible schedules to the above problem.  Specifically, there are 3! feasible schedules, as the only thing that characterizes a feasible schedule is the order that the jobs are placed.  These are the 6 feasible schedules for the above problem:

Screenshot 2015-01-02 20.42.16

This means that for any objective function, we can simply produce all feasible schedules (since there are only finitely many), and find the one with the best objective value.  However, since there are n! feasible schedules, this process will take longer than we would like (what we want is polynomial time!!).  For many objective functions, there exist very efficient algorithms to find optimal or near-optimal solutions.

Lateness and Tardiness

To do a simple example, we must first define the notion of lateness and tardiness.

Given a specific schedule, denote C_j as the completion time of job j.
Then, we can define the concept of lateness, L_j, as

L_j=C_j-d_j

So a job’s lateness is 2 if the job was completed 2 time units after its deadline.

Note that with this definition, a job can have a negative lateness, which implies the job was early.  This notion of a negative lateness may seem unintuitive; thus we create another definition called tardiness.

T_j= max\{0, L_j\}

Tardiness is never negative. Hence it is equal to lateness if the job is late, but is 0 if the job is early or on time. Thus, L_j <= T_j for any specific job in a schedule.

Examples of Objective Functions

With the above definitions set, let’s try to minimize the following functions:

L_{max} = max\{\,L_j\>|\>j \in \{1,2,...,n\}\}

T_{max} = max\{\,T_j\> |\>j \in \{1,2,...,n\}\}

Given a specific schedule, L_{max} is the value of the lateness of the job that is the most late. (Same for T_{max} with tardiness.)

We denote L_{max}* and T_{max}* to be the value of the optimal solution for L_{max} and T_{max} respectively. (We know that the optimal values exist since there are only finitely many feasible schedules.)

Optimal L_{max} implies optimal T_{max}

Note that finding an optimal schedule for L_{max} corresponds to an optimal solution for T_{max} given the same problem.

  • If L_{max}* \leq 0, then T_{max} = 0 for that schedule, which is optimal since T_{max}* \geq 0.
  • If L_{max}* > 0, then T_{max} =L_{max}* and L_{max}* \leq T_{max}* (this inequality always holds).  Since we are minimizing T_{max} and T_{max} \leq T_{max}* , we get that this T_{max} is optimal.

However, the converse is not true.  Finding an optimal solution for T_{max} does not correspond to an optimal solution for L_{max} given the same problem.  Here is a counterexample:

Screenshot 2015-01-01 18.46.03With the above numbers, it turns out that any schedule gives an optimal T_{max}.  No matter how the jobs are placed, all jobs always finish by time 3.  Since all the deadlines are \ge 3, all jobs will always be early or on time.  So T_{max}=T_{max}*=0 for all feasible schedules.

However, since L_{max} cares about how early a job is, there is only one optimal solution for L_{max}, which is:

Screenshot 2015-01-01 18.30.42
with L_{max}* = -2.

So it is not true that a schedule that optimizes T_{max} also optimizes L_{max}.

Optimal Algorithm for L_{max} and T_{max}

When given a set of jobs and deadlines, the most intuitive way to schedule them would be to schedule the one that has the earliest due date first.  It turns out that this method gives the optimal schedule for both L_{max} and T_{max}.

Concretely, if  \,d_{[i]}\, is the due date of the i'th job in a schedule, then a schedule such that d_{[1]} \leq d_{[2]} \leq ...\leq d_{[n]} yields an optimal schedule for L_{max} and T_{max}.  This can be proven using contradiction.

This is great!  Now we have a very efficient algorithm to optimize L_{max} and T_{max} for any given problem.

Unfortunately, those objective functions are not terribly useful.  With the above objective functions, having one job late by 3 units and the rest of the jobs early, is worse than having all the jobs late by 2 time units.  This does not seem entirely intuitive.  Hence we can define a new set of objective functions: the sum of the lateness and tardiness for every job.

New Objective Functions: \sum L_{j}, \sum T_{j}

To optimize \sum L_{j}, one simply has to order the jobs in non-decreasing processing time. (i.e. Do the shortest jobs first!) If \>p_{[i]}\> is the processing time of the i'th job in a schedule, a schedule is optimal if and only if p_{[1]} \leq p_{[2]} \leq ...\leq p_{[n]}. (Note that this is an if and only if, whereas the last algorithm was not.)

So optimizing \sum L_{j} turned out to be another very simple algorithm. What about \sum T_{j} ?

Finding the optimal solution for \sum T_{j} turns out to be NP-hard.  Although lateness, L_{j}, and tardiness, T_{j}, are very similar functions, it turns out that tardiness is much harder to deal with.  With a dynamic programming approach, the best we can get for \sum T_{j} is pseudo-polynomial time.  I won’t go into details of this algorithm, but it is definitely much harder than solving \sum L_{j}.


 

The above is probably what you would learn in the first two classes if you were to take scheduling (CO 454).  In the course, you learn about many more different scheduling problems and their corresponding algorithms/proofs to solve them.  In addition, you learn about various techniques such as dynamic programming or approximation algorithms to solve the problems that have no efficient solution.  The course had a very good mix of rigorous content, applicable material, and algorithms.  I highly recommend it!