Prev Next

Task Scheduling

Consider tasks 1, 2, ..., n with running times of t1, t2, ..., tn. What is the best way to schedule them in order to to minimize the completion time?

Example

Consider the problem stated as (i, ti) pairs: (1,15), (2,8), (3,3), (4,10).

(1) Brute-force solution

The brute-force way to solve this problem is to consider all possible ways to schedule them, compute the completion time for each possibility and determine the minimum one. Given n tasks, there are n! ways to schedule them. Hence the time complexity is Θ(n!).

For the above example there are 24 ways to schedule them.

  • 1234, 1243, 1324, 1342, 1423, 1432
  • 2134, 2143, 2314, 2341, 2413, 2431
  • 3124, 3142, 3412, 3421, 3214, 3241
  • 4123, 4132, 4213, 4231, 4312, 4321

Consider the task schedule 1234. The completion time of the tasks can be determined as:

    = t1 + (t1 + t2) + (t1 + t2 + t3) + (t1 + t2 + t3 + t4)
    = 4t1 + 3t2 + 2t3 + t4 ................(Equation 1)
    = 4*15 + 3*8 + 2*3 + 10
    = 60 + 24 + 6 + 10
    = 100

The brute-force solution can be implemented using recursion.

	// Task scheduling
	Schedule(Tasks 1..n) {
		if (n == 0)
			return
		for (i = 1; i <= n; i++) {
			Perform the ith task
			Schedule(Tasks 1..i-1,i+1..n)  // excludes task i
		}
	}

The recursion tree for the above example is as follows. Each call path from the root to the leaf shows one of the 4! = 24 ways of scheduling the tasks.


                                                              |-- Schedule(4) -- Schedule(.)  [100]
                                          |-- Schedule(3,4) --|
                                          |                   |-- Schedule(3) -- Schedule(.)  [107]
                                          |
                                          |
                                          |                   |-- Schedule(3) -- Schedule(.)
                    |-- Schedule(2,3,4) --|-- Schedule(2,3) --|
                    |                     |                   |-- Schedule(2) -- Schedule(.)
                    |                     |
                    |                     |
                    |                     |                   |-- Schedule(4) -- Schedule(.)
                    |                     |-- Schedule(2,4) --|
                    |                                         |-- Schedule(2) -- Schedule(.)
                    |
                    |
                    |
                    |                                         |-- Schedule(4) -- Schedule(.)
                    |                     |-- Schedule(3,4) --|
                    |                     |                   |-- Schedule(3) -- Schedule(.)
                    |                     |
                    |                     |
                    |                     |                   |-- Schedule(3) -- Schedule(.)
                    |-- Schedule(1,3,4) --|-- Schedule(1,3) --|
                    |                     |                   |-- Schedule(1) -- Schedule(.)
                    |                     |
                    |                     |
                    |                     |                   |-- Schedule(4) -- Schedule(.)
                    |                     |-- Schedule(1,4) --|
                    |                                         |-- Schedule(1) -- Schedule(.)
                    |
Schedule(1,2,3,4)-- |
                    |
                    |                                         |-- Schedule(2) -- Schedule(.)
                    |                     |-- Schedule(1,2) --|
                    |                     |                   |-- Schedule(1) -- Schedule(.)
                    |                     |
                    |                     |
                    |                     |                   |-- Schedule(4) -- Schedule(.)
                    |-- Schedule(1,2,4) --|-- Schedule(1,4) --|
                    |                     |                   |-- Schedule(1) -- Schedule(.)  [71] <== MINIMAL
                    |                     |
                    |                     |
                    |                     |                   |-- Schedule(4) -- Schedule(.)
                    |                     |-- Schedule(2,4) --|
                    |                                         |-- Schedule(2) -- Schedule(.)
                    |
                    |
                    |
                    |                                         |-- Schedule(3) -- Schedule(.)
                    |                     |-- Schedule(2,3) --|
                    |                     |                   |-- Schedule(2) -- Schedule(.)
                    |                     |
                    |                     |
                    |                     |                   |-- Schedule(2) -- Schedule(.)
                    |-- Schedule(1,2,3) --|-- Schedule(1,2) --|
                                          |                   |-- Schedule(1) -- Schedule(.)
                                          |
                                          |
                                          |                   |-- Schedule(3) -- Schedule(.)
                                          |-- Schedule(1,3) --|
                                                              |-- Schedule(1) -- Schedule(.)

Time complexity

Since there are n! ways of scheduling the tasks, the time complexity T(n) = Θ(n!).

(2) Greedy Solution

To apply greedy strategy we need to first check if the problem exhibits (i) optimal substructure property and (ii) greedy choice property.

Optimal substructure: The recursive fomulation above reveals the optimal substructure. The problem of solving the task scheduling of n tasks optimally contains within itself the problem of sovling the subproblems of n-1 tasks.

Greedy choice property: In the above recursive solution, we reduced the problem of size 4 to four subproblems, each of size 3. Solution to exactly one of these 4 subproblems ultimately led to the optimal solution for the problem. Is there a way to determine which of the 4 would lead to optimal solution and eliminate the other 3 subproblems? In other words, can we make a sequence of locally optimal choices that leads to globally optimal solution?

Yes. As per Equation 1, if the shorter job is scheduled earlier, it reduces the overall, completion time. This can be made use of in deciding which task to schedule. In the above example, the optimal order is 3 -> 2 -> 4 -> 1. This is guaranteed to provide the minimum completion time.

Therefore, minimum completion time = 4*3 + 3*8 + 2*10 +1*15 = 71.

The algorithm for greedy solution is given below. Let T[1..n] denote the time taken for each task. We first sort the tasks based on the time it takes to complete each of them. We iterate through the sorted array to compute the completion time.

	// Greedy algorithm for Task Scheduling
	GreedySchedule(T[1..n]) {
		T.sort()
		completiontime = 0; weight = n;

		for (i = 1; i <=n; i++) {
			completiontime += weight * T[i]
			weight--
		}
	}

Time complexity

Sorting takes O(nlogn) and iterating through the array n times to compute the completion time takes n * O(1) = O(n) time. Hence, the time complexity is O(nlogn).

(3) Dynamic Programming Solution

When a greedy solution exists, dynamic programming solution is unnecessary since greedy strategy provides the fastest way to solve optimization problems. However, in this section we discuss the dynamic programming solution.

To apply dynamic programming, we need to check if the problem exhibits (i) optimal substructure and (ii) overlapping subproblems.

(i) We already saw above, while discussing the greedy solution, that optimal substructure property holds. i.e. optimal solution to the scheduling problem contains within itself optimal solution to the subproblems.

(ii) The recursive formulation also reveals the existence of overlapping subproblems. Schedule(1,2) is repeated twice. Schedule(1) is repeated 6 times. In other words, for n = 4, the subproblems of size 2 repeat twice while subproblems of size 1 repeats 6 times. For large values of n, the number of overlapping subproblems are going to be far higher. Dynamic programming computes the subproblems exactly once.

Bottom-up approach

The dynamic programming works in a bottom-up fashion. Subproblems are solved and their solutions are used to find solutions to larger problems. Hence, we work as follows.

  • If we are allowed to schedule only one task, what is the optimal order?
  • Next we allow two consecutive tasks to be scheduled and find what is the optimal order.
  • Next we allow three consecutive tasks to be scheduled and find what is the optimal order.
  • So on and so forth ... until n consecutive tasks which computes the optimal order for all tasks.

Let Schedule[i,j] denote the optimal order to schedule jobs from i to j. Initially, j = i. In the subsequent iterations, j takes the values of (i+1), (i+2), ..., (i+n-1). This can be consolidated by defining a special variable 'len' which takes values 0 through n-1 denoting the length of consecutive tasks considered for that iteration. And hence, j = i + len for len = 0...n-1.

  • For the first iteration len = 0, we find the optimal order for the range [i,i].
    i.e. Schedule[1,1], Schedule[2,2], ..., Schedule[n,n].       (n computations)
  • For the second iteration len = 1, we find the optimal order for the range [i,i+1].
    i.e. Schedule[1,2], Schedule[2,3], ..., Schedule[n-1,n].     (n-1 computations)
  • For the third iteration len = 2, we find the optimal order for the range [i,i+2].
    i.e. Schedule[1,3], Schedule[2,4], ..., Schedule[n-2,n].     (n-2 computations)
  • ....
  • ....
  • For the last but one iteration len = n-2, we find the optimal order for the range [i,i+n-2].
    i.e. Schedule[1,n-1], Schedule[2,n]       (2 computations)
  • For the last (nth) iteration len = n-1, we find the optimal order for [i,i+n-1].
    i.e. Schedule[1,n].         (1 computation)

The entire computation worked out above can be accomplished using the following nested loop.

    for (len = 0; len < n; len++) {
        for (i = 1; i <= n-len; i++) {
            j = i + len
            // Determine Schedule[i,j]
            .............
            .............
        }
    }

Iteration 1: len = 0; i = 1 to n; j = i+len = i;

Considering each task individually, there exists exactly one way to order each of them. Schedule[i,i] = { i }.

Let us now work out for the given example.

    Schedule[1,1] = {1}

    Schedule[2,2] = {2}

    Schedule[3,3] = {3}

    Schedule[4,4] = {4}


    i \ j

    		  j = 1   j = 2   j = 3   j = 4 
      i = 1  
    Schedule[1,1] =
    {1}
      i = 2  
    Schedule[2,2] =
    {2}
      i = 3  
    Schedule[3,3] =
    {3}
      i = 4  
    Schedule[4,4] =
    {4}

Iteration 2: len = 1; i = 1 to n-1; j = i+len = i+1

In this iteration, we compute Schedule[i,i+1]. Having computed Schedule[i,i] in the previous iteration, we want to insert job i+1 to the already optimal Schedule[i,i]. There exists exactly two possibilities.

  1. Schedule[i,i] o {i+1}. i.e. insert (i+1)th job after (the already optimal) Schedule[i,i].
  2. {i+1} o Schedule[i,i]. i.e. insert (i+1)th job before (the already optimal) Schedule[i,i].

The next question is how to determine which insertion is optimal. This can be determined by checking whether ti < ti+1.

  • If TRUE, Schedule[i,i] o {i+1} = {i} o {i+1} = {i, i+1} is optimal.
  • If FALSE, {i+1} o Schedule[i,i] = {i+1} o {i} = {i+1, i} is optimal.

Let us now work out Schedule[1,2], Schedule[2,3], Schedule[3,4] for given example.

    Schedule[1,2] = Schedule[1,1] o {2} OR {2} o Schedule[1,1]
    Since t1 ≮ t2, Schedule[1,2] = {2} o Schedule[1,1] = {2, 1}

    Schedule[2,3] = Schedule[2,2] o {3} OR {3} o Schedule[2,2]
    Since t2 ≮ t3, Schedule[2,3] = {3} o Schedule[2,2] = {3, 2}

    Schedule[3,4] = Schedule[3,3] o {4} OR {4} o Schedule[3,3]
    Since t3 < t4, Schedule[3,4] = Schedule[3,3] o {4} = {3, 4}


    i \ j

    		  j = 1   j = 2   j = 3   j = 4 
      i = 1  
    Schedule[1,1] =
    {1}
    Schedule[1,2] =
    {2,1}
      i = 2  
    Schedule[2,2] =
    {2}
    Schedule[2,3] =
    {3,2}
      i = 3  
    Schedule[3,3] =
    {3}
    Schedule[3,4] =
    {3,4}
      i = 4  
    Schedule[4,4] =
    {4}

Iteration 3: len = 2; i = 1 to n-2; j = i+len = i+2

In this iteration, we compute Schedule[i,j] where j = i+2. i.e. Schedule[i,i+2]. Having computed optimal Schedule[i,j-1] (or equivalently Schedule[i,i+1]), we want to insert the task j to the already optimal Schedule[i,j-1] (or equivalently Schedule[i,i+2]). There are exactly four possibilities.

    1. Insert j before Schedule[i,j-1]. i.e. {j} o Schedule[i,j-1]

    2. Insert j after Schedule[i,j-1]. i.e. Schedule[i,j-1] o {j}

    3. Insert j between Schedule[i,i] and Schedule[j-1,j-1]. i.e. Schedule[i,i] o {j} o Schedule[j-1,j-1]

    4. Insert j between Schedule[j-1,j-1] and Schedule[i,i]. i.e. Schedule[j-1,j-1] o {j} o Schedule[i,i]

One might notice that 2 is the reflection of 1 and 4 is the reflection of 3. The next question is which of the four insertions is optimal.

    1. If tj < MIN{ti,tj-1}, Schedule[i,j] = {j} o Schedule[i,j-1]

    2. If tj > MAX{ti,tj-1}, Schedule[i,j] = Schedule[i,j-1] o {j}

    3. if ti < tj < tj-1, Schedule[i,j] = Schedule[i,i] o {j} o Schedule[j-1,j-1]

    4. if ti > tj > tj-1, Schedule[i,j] = Schedule[j-1,j-1] o {j} o Schedule[i,i]

Let us now work out Schedule[1,3] and Schedule[2,4] for the given example.

    t3 = 3 < MIN{t1, t2} = MIN{15, 8} = 8. Hence, Schedule[1,3] = {3} o Schedule[1,2] = {3} o {2,1} = {3,2,1}

    t4 = 10 > MAX{t2, t3} = MAX{8, 3} = 3. Hence, Schedule[2,4] = Schedule[2,3] o {4} = {3,2} o {4} = {3,2,4}


    i \ j

    		  j = 1   j = 2   j = 3   j = 4 
      i = 1  
    Schedule[1,1] =
    {1}
    Schedule[1,2] =
    {2,1}
    Schedule[1,3] =
    {3,2,1}
      i = 2  
    Schedule[2,2] =
    {2}
    Schedule[2,3] =
    {3,2}
    Schedule[2,4] =
    {3,2,4}
      i = 3  
    Schedule[3,3] =
    {3}
    Schedule[3,4] =
    {3,4}
      i = 4  
    Schedule[4,4] =
    {4}

Iteration 4: len = 3; i = 1 to n-3; j = i+len = i+3

In this iteration, we compute Schedule[i,j] where j = i+3. i.e. Schedule[i,i+3]. Having computed optimal Schedule[i,j-1], we want to insert task j to the already optimal Schedule[i,j-1]. There are exactly six possibilities. Before proceeding further, note the following connection between i and j for len = 3.

i = j - 3

i + 1 = j - 2

i + 2 = j - 1

i + 3 = j

The six possibilities are stated below.

    1. Insert j before Schedule[i,j-1]. i.e. {j} o Schedule[i,j-1]

    2. Insert j after Schedule[i,j-1]. i.e. Schedule[i,j-1] o {j}

    3. Insert j between Schedule[i,i] and Schedule[i+1,j-1]. i.e. Schedule[i,i] o {j} o Schedule[i+1,j-1]

    4. Insert j between Schedule[i+1,j-1] and Schedule[i,i]. i.e. Schedule[i+1,j-1] o {j} o Schedule[i,i]

    5. Insert j between Schedule[i,i+1] and Schedule[i+2,j-1]. i.e. Schedule[i,i+1] o {j} o Schedule[i+2,j-1]

    6. Insert j between Schedule[i+2,j-1] and Schedule[i,i+1]. i.e. Schedule[i+2,j-1] o {j} o Schedule[i,i+1]

2 is the reflection of 1, 4 of 2 and 6 of 5. The next question is which of the six insertions is optimal.

    1. If tj < MIN{ti, .., tj-1}, Schedule[i,j] = {j} o Schedule[i,j-1]

    2. If tj > MAX{ti, .., tj-1}, Schedule[i,j] = Schedule[i,j-1] o {j}

    3. If ti < tj < MIN{ti+1,tj-1}, Schedule[i,j] = Schedule[i,i] o {j} o Schedule[i+1,j-1]

    4. If ti > tj > MAX{ti+1,tj-1}, Schedule[i,j] = Schedule[i+1,j-1] o {j} o Schedule[i,i]

    5. If MIN{ti,ti+1} < tj < tj-1, Schedule[i,j] = Schedule[i,i+1] o {j} o Schedule[i+2,j-1]

    6. If MAX{ti,ti+1} > tj > tj-1, Schedule[i,j] = Schedule[i+2,j-1] o {j} o Schedule[i,i+1]

Let us now work out Schedule[1,4] for the given example.

    t1 = 15 > t4 = 10 > MAX{t2,3} = 8 (Case 4). Hence Schedule[1,4] = Schedule[2,3] o {4} o Schedule[1,1] = {3, 2} o {4} o {1} = {3, 2, 4, 1}


    i \ j

    		  j = 1   j = 2   j = 3   j = 4 
      i = 1  
    Schedule[1,1] =
    {1}
    Schedule[1,2] =
    {2,1}
    Schedule[1,3] =
    {3,2,1}
    Schedule[1,4] =
    {3,2,4,1}
      i = 2  
    Schedule[2,2] =
    {2}
    Schedule[2,3] =
    {3,2}
    Schedule[2,4] =
    {3,2,4}
      i = 3  
    Schedule[3,3] =
    {3}
    Schedule[3,4] =
    {3,4}
      i = 4  
    Schedule[4,4] =
    {4}

Generalizing the computation of Schedule[i,j] for each i,j.

We observed the following from the above iterations. The first iteration does not need any computation. While during the other iterations, we perform computations that can be summarized as follows.

    1. Either we insert task j before/after Schedule[i,j-1] or somewhere between Schedule[i,j-1]

    2. Inserting before Schedule[i,j-1] is the reflection of inserting after Schedule[i,j-1]
        - {j} o Schedule[i,j-1] is the reflection of Schedule[i,j-1] o {j}
        - So, one can be derived from the other.

    3. Inserting between Schedule[i,k] and Schedule[k+1,j-1] is the reflection of inserting between Schedule[k+1,j-1] and Schedule[i,k]
        - Schedule[i,k] o {j} o Schedule[k+1,j-1] is the reflection of Schedule[k+1,j-1] o {j} o Schedule[i,k]
          for some k between i and j-2
        - So, one can be derived from the other.

    4. Bullets 2 and 3 can be combined by allowing k to range from i-1 to j-2 (instead of i to j-2). And therefore one if (test) is sufficient. The else part takes care for the reflection case.
        - Note that when k = i-1, Schedule[i,k] = Schedule[i,i-1] which returns an empty set since i-1 < i.

    5. Finding MIN{ti,tk} can be computed instantly by picking the first entry in Schedule[i,k] and finding its time. i.e. tfirst_entry_of_Schedule[i,k].

    6. Finding MAX{ti,tk} can be computed instantly by picking the last entry in Schedule[i,k] and finding its time. i.e. tlast_entry_of_Schedule[i,k].

Algorithm

The dynamic programming algorithm for task scheduling can be given as follows.

	int Schedule[n][n];

	TaskSchedule(t[1..n]) {
	  for (i = 1; i <= n; i++)	// Iteration 1
		Schedule[i][i] = {i};

	  for (len = 0; len < n; len++) {	// Iteration 2 through n
		for (i = 1; i <= n-len; i++) {
	      j = i + len;

	      /* Computing Schedule[i][j] for each k - Either if ... 
	      or else if ... condition will be true for some k */

		  for (k = i-1; k < j-1; k++) {			  								
			if ( MAX{t[i..k]} < t[j] < MIN{t[k+1..j-1]} )
		      Schedule[i][j] = Schedule[i][k] o {j} o Schedule[k+1][j-1];
			else if ( MIN{t[i..k]} > t[j] > MAX{t[k+1..j-1]} )
			  Schedule[i][j] = Schedule[k+1][j-1] o {j} o Schedule[i][k];
		  }
		}
	  }
	}

Time complexity

There are 3 loops. The outerloop runs n times. The inner loop runs at most n times. And finally, the innermost loop runs for at most n times. Thus, the time complexity is O(n3).