Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 9

(a)

The completion times are (4, 6, 14, 15). So, the ACT is (4 + 6 + 14 + 15) / 4) = 9.75.

(b)

When the task order is 2, 1, 4, 3, the completion times are (2, 6, 7, 15). Now, the ACT is (2 + 6 + 7 + 15) / 4 = 7.5.

(c)

For the greedy order 4, 2, 1, 3, the completion times are (1, 3, 7, 15). The ACT for this order is 26 / 4 = 6.5.

(d)

The greedy strategy can be implemented in n log n time by using an O(n log n) sorting algorithm to first sort the tasks into ascending order of task time. This sorted order is the order in which the tasks are to be done. The code to minimize the ACT is given below.

---

public class AverageCompletionTime
{
   // top-level nested class
   static class Task implements Comparable
   {
      // instance data members
      int time;                  // task length
      int id;                    // task id

      // constructor
      Task(int theTime, int theId)
      {
         time = theTime;
         id = theId;
      }

     // method of Comparable
     /** return true iff this < x */
     public int compareTo(Object x)
     {
        int xTime = ((Task) x).time;
        if (time < xTime)
           return -1;
        if (time == xTime)
           return 0;
        return 1;
      }
  
     /** return true iff this == x */
     public boolean equals(Object x)
        {return time == ((Task) x).time;}
     }

   
   /** reorder the tasks task[1:task.length-1] so that the
     * average completion time is minimized */
   public static void minimizeAverageCompletionTime(Task [] task)
      {HeapSort.heapSort(task);}
}

The code and a sample test can be found in the files AverageCompletionTime.*.

(e)

Since there are only n! orders in which the n tasks can be done, there must be one with minimum ACT. Let S denote the order that gives minimum ACT. Consider the tasks in the order given by S. Suppose there is an i for which ti > ti+1. Let A = t1 + t2 + ... + ti-1. The ACT of S is

((c1 + ... + ci-1) + ci + ci+1 + (ci+2 + ... + cn)) / n
= ((c1 + ... + ci-1) + A + ti + A + ti + ti+1 + (ci+2 + ... + cn)) / n
= ((c1 + ... + ci-1) + 2A + 2ti + ti+1 + (ci+2 + ... + cn)) / n.

If we swap tasks i and i+1, the ACT becomes ((c1 + ... ci-1) + 2A + ti + 2ti+1 + (ci+2 + ... + cn)) / n. Since ti > ti+1, the ACT is reduced as a result of the swap. So, S does not have minimum ACT. This contradicts the assumption that S has minimum ACT. So, there can be no i, in S, for which ti > ti+1. As a result, the tasks in S are in nondecreasing order of task times.

When several tasks have the same task time, the relative order of these does not affect the ACT. So, any sorted order may be used. As a result, the task order generated by the greedy strategy of (c) has minmum ACT.