Bounding schemes for the parallel machine scheduling problem with DeJong's learning effect

In this paper, the parallel machine scheduling problem with DeJong's learning effect, is addressed. The objective function to be minimized is the makespan. This problem is proofed to be NP-Hard in the strong sense. This is the challenging theoretical side of the studied problem. Furthermore, several real life situations in manufacturing and computer science are modeled using the current problem. Several algorithms intended to solve the studied problem within a reasonable computing time are proposed in literature. Among these algorithms the exact methods, which failed to solve the studied problem to optimality even for small size instances. In this paper several new heuristics and meta-heuristics are proposed. These heuristics are classified into three types. The first type is based on Longest Processing Time (LP T) rule. The innovation is the modification of the LP T rule in a way to cope efficiently with the learning effect concept, by randomizing the selection of the next scheduled job. The second type of heuristics, is taking advantage of an exact Branch and Bound algorithm, developed originally for the classical parallel machine scheduling problem. The contribution for this kind of heuristics is lying in the modification of the processing time values, according to a prefixed selected functions. The third type of methods is based in an adaptation of the Genetic Algorithm to the learning effect concept. This adaptation consists in enlarging the area of selection of the parameters values. To assess the performance and the efficiency of the proposed heuristics, a newly developed lower bound is proposed. This lower bound is based on a relaxation of the studied problem, which allows to obtain a minimum cost flow problem. Finally, an extensive experimental study is conducted over a benchmark test problems. The obtained results provide strong evidence that the proposed procedures outperform the earlier existing ones. (c) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper addresses the parallel machine scheduling problem with DeJong's learning effect, proving it to be NP-Hard. New heuristics are proposed and experimentally shown to outperform earlier methods.