title: Scheduling, Greedy algorithm
body: <p>This is a variation of the popular El Goog problem.</p>
  
  <hr>
  
  <p>Consider the following scheduling problem: There are n jobs, i = 1..n. There is 1 super computer and unlimited PCs. Each job needs to be pre-processed by the super computer first and then processed on a PC. The time required for job i on the super computer is si, i = 1..n. For PCs, it's pi, i = 1..n. The PCs can work in parallel, but the super computer can only work on 1 job at a time. A schedule S is created according to which the super computer will process the jobs. The completion time Ti(S) in schedule S is given by the clock time at which the job finishes on the PC. We want to find a schedule that minimizes Maxi[Ti(s)] <em>(to be read as: we need to find a schedule that minimizes the highest finish time)</em>. The following greedy algorithm is proposed: Arrange the jobs in the decreasing order of processing times on the PCs. The complexity of this algorithm is O(nlogn). Either prove that this algorithm produces an optimal solution or provide a counter-example to show that it does not.</p>
  
  <hr>
  
  <p>My solution (not sure if this is correct): I don't think it matters how we order the jobs. The highest finish time will still be the same. Consider this example of the processing times on the PCs for a list of jobs: &lt;5, 7, 17, 8, 10>. This will yield finish times as &lt;5, 12, 29, 37, 47>. As per the algorithm, we will sort the list as &lt;17, 10, 8, 7, 5> and will yield finish times of &lt;17, 27, 35, 42, 47>. So while technically, the greedy algorithm does give an optimal ordering, it takes nlogn time to do that, while simply iterating through the list of jobs gives us the same result.</p>
  
  <p>If anyone thinks that the greedy algorithm will work better or that my approach is flawed, I'd appreciate your thoughts.
  Thanks!</p>
  
  <hr>
  
  <p><strong>Update</strong>: I think I may have the answer. The time taken by the super computer doesn't matter. The key here is that the PCs run in <em>parallel</em>. From the initial example of pi = &lt;5, 7, 17, 8, 10>, let's add si = &lt;8, 5, 1, 12, 9>. Now, in the default, unsorted order, we'd have processing times of &lt;13, 20, (8 + 5 + 1 + 17 = )31, 34, 45>. So 45 is the time of completion. Assume a sorted order in which pi's are decreasing. The output is: &lt;18, 20, 30, 34, 40>. [Sorted input: pi = &lt;17, 10, 8, 7, 5>, si = &lt;1, 9, 12, 5, 8>].</p>
  
  <p>Here's an example that probably clears the whole thing up:
  si = &lt;17, 10>, pi = &lt;10, 17>. The output in the unsorted case (which also happens to be sorted in descending order of si) will be &lt;27, 44>. Sorting based on pi, the input is: si = &lt;10, 17>, pi = &lt;17, 10>. Output is &lt;27, 37>. Since the PCs run in parallel, you want to send the shortest job last.</p>