Minimization of maximum lateness on parallel machines with a single server and job release dates
4OR, Year 2023
Notification
URL copied to clipboard!
This paper addresses the problem of scheduling independent jobs with release dates on identical parallel machines with a single server. The goal consists in minimizing the maximum lateness. This is a realistic extension of the traditional parallel machine scheduling problem with a single server, in which all jobs are assumed to be available at the beginning of the schedule. This problem, referred to as P, S1 | rj| Lmax , has various applications in practice. To date, research on it has focused on complexity analysis. To solve small-sized instances of the problem, we present two mixed-integer-programming formulations, along with a valid inequality. Due to the NP -hard nature of the problem, we propose a constructive heuristic and two metaheuristics, namely a General Variable Neighborhood Search (GVNS) and a Greedy Randomized Adaptive Search Procedures, both using a Variable Neighborhood Descent as an intensification operator. In the experiments, the proposed algorithms are compared using a set of new instances generated randomly with up to 500 jobs, in line with the related literature. It turns out that GVNS outperforms by far the other approaches.