On a parallel machine scheduling problem with equal processing times

What is it about?

In this note, we give a polynomial algorithm for solving the scheduling problem problem on identical parallel machines, equal processing times and arbitrary release times of the jobs such that the sum of job-specific (cost) functions depending on the completion times of the jobs is minimized assuming that for any two jobs, the difference of the two functions is monotonic.

Featured Image