Lets just say I have two lists of the running time of tasks A and B. Formally, I would have:
A = {a_1, a_2, a_3 ... a_n}
B = {b_1, b_2, b_3 ... b_n}
I can only have one task from A running at any one time. All other tasks in A have to wait on that task to complete before they can be released. I can have any amount of tasks from B running at any one time, however I cannot run a task from B if its equivalent task from A has not finished. For example, I could not run b_1 if a_1 had not finished beforehand.
To put this in an analogy, say that I have some athletes who will perform a di(duo?)athlon: they will run laps on a running field then cycle for some distance. Only one athlete can be running laps on the field at any one time, and only after he or she has finished can he or she proceed to cycling. Any amount of athletes can be cycling at any one time. In this case, A would be the amount of time I know an athlete will take to run their laps around the field and B would be the amount of time I know it will take them to cycle the required distance.
I would like create an algorithm which devises a schedule for my tasks (or for my athletes) so that the total time it takes for all of them to complete their activities is kept to a minimum.
The basic jist is this: The time it takes for any individual athlete to complete their tasks is running_time + cycling_time + waiting_time. The running and cycling times I know, while the waiting time would be the sum of all running times of all athletes prior to the current one, i.e. For some athlete a_i the waiting_time = a_1 + a_2 + a_3 + ... + a_(i-1). Intuitively, I would like the athletes with shorter running times and longer cycling times to go first since I want to maximize the amount of athletes cycling at any one time.
My question is: how would I go about doing this? How would I schedule my tasks (athletes)? Obviously, I could go about computing every single possibility and picking the best one, but that would result in some ludicrous O(2^n) algorithm. Subsequently, (it seems?) a greedy algorithm would be the best choice.
EDIT: A few days later.
The way (again, I believe) that seems to be the most optimal is this:
Let a_max = a_1 + a_2 + ... + a_n - a_i. Informally, this is to say that a_max is the worst-case waiting time for a task/athlete i. Then, let completion_time_for_i = a_max + b_i. We compute completion_time_for_i for each task/athlete and order it in a descending fashion. That is to say, tasks/athletes with larger completion_time_for_i will be up a the top of the schedule, while tasks/athletes with lower completion_time_for_i will be lower down on the schedule.
The point is that a_max is larger the smaller a_i is and completion_time_for_i will be largest for tasks/athletes with the greatest difference between their running and biking times. Hence, we are doing what intuition suggests: putting the tasks/athletes with shorter running times and longer biking times first.
Of course, I cannot escape the math, can I? I'm not even entirely certain where to start my proof to show if this algorithm is "correct". I guess it would be something along the lines of: my schedule takes x time. The greedy algorithm is incorrect if there exists a y such that y > x. However (assuming that my algorithm is correct) I cannot construct a schedule which takes y time and hence the proof by contradiction (as suggested in the link from @D.W.).
