Exact and heuristic algorithms for parallel-machine scheduling with DeJong’s learning effect

We consider a parallel-machine scheduling problem with a learning effect and the makespan objective. The impact of the learning effect on job processing times is modelled by the general DeJong’s learning curve. For this NPNP-hard problem we propose two exact algorithms: a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. We also present the results of experimental evaluation of these algorithms on a computational cluster. Finally, we use the exact algorithms to estimate the performance of two greedy heuristic scheduling algorithms for the problem.