Minimizing the makespan for the two-machine scheduling problem with a single server: Two algorithms for very large instances

What is it about?

The paper presents two constructive polynomial heuristics for the problem of scheduling a set of jobs on two identical parallel machines with a single server. These fast algorithms of quadratic complexity yield excellent results for large instances of several thousands of jobs.

Featured Image

Why is it important?

Among the algorithms suggested in the previous years for this problem, these heuristcs yield clearly the best results. The deviation from the lower bound is almost zero and it becomes even smaller with increasing size of the problem. There is no other algorithm for this problem treating instances of 10000 jobs.