My problem seems similar to the Interval Scheduling problem (processing as many jobs as possible), which I understand but can't seem to apply properly in this case. I've tried to simplify the problem as much as I can:
There are n jobs, each of which must be processed first on computer A and then on computer B. Each job has two specific processing times, one for each computer. Computer A can process one job at a time while computer B can process an unlimited number of jobs at the same time. Using a greedy algorithm, how can the jobs be ordered such that the total processing time of all the jobs is minimized and how can that algorithm be proven to be the optimal solution?
For example, say that there are 3 jobs with the following process times for each computer:
i = 1, A(1) = 05, B(1) = 20
i = 2, A(2) = 10, B(2) = 10
i = 3, A(3) = 20, B(3) = 05
All the jobs will be out of computer A after 35 seconds regardless of the order in which they are started, but that order will affect the overall finish time. For example, running the jobs in the order given takes 40 seconds to finish, while running the jobs in the reverse order takes 55 seconds. So in this example, the optimal solution is to run the jobs in the given order.
I'm fairly certain that the "algorithm" is to simply sort the jobs by their B processing time from longest to shortest, but I'm having a hard time proving it. I'm getting caught up with my greedy algorithm taking the "longest" job first, which doesn't seem very greedy. And then to use an inductive proof I would need begin by showing that my algorithm works for just the first job, which I would think is not obvious until the end. Maybe I need to start the proof with the final job and work backwards? Any help would be greatly appreciated.