I have the following problem:
We have a set of tasks that requires some preprocessing time. When the job is preprocessed, the job can be executed on a parallel thread that also requires some time. The preprocessing can only be done on a single thread and cannot be multi-threaded.
My task was to give a greedy algorithm that determines a schedule that minimizes the latest end time. I thought this could be accomplished with a schedule that schedules jobs according to their parallel processing time (the ones with the longest parallel processing time first).
Now I have to prove that this algorithm works by giving an exchange argument. I've read the book but I'm not sure on where to start (I'm very bad in proving things). Suppose that we have an optimal schedule S. When using an exchange argument, I have to transform this optimal schedule to the greedy one that my algorithm returns.
Could anyone please give me a hand?