Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations

In many situations, a worker's ability improves as a result of repeating the same or similar task; this phenomenon is known as the “learning effect”. In this paper, the learning effect is considered in a single-machine maximum lateness minimization problem. A branch-and-bound algorithm, incorporating several dominance properties, is provided to derive the optimal solution. In addition, two heuristic algorithms are proposed for this problem. The first one is based on the earliest due date (EDD) rule and a pairwise neighborhood search. The second one is based on the simulated annealing (SA) approach. Our computational results show that the SA algorithm is surprisingly accurate for a small to medium number of jobs. Moreover, the SA algorithm outperforms the traditional heuristic algorithm in terms of quality and execution time for a large number of jobs.