Portal de Periódicos da CAPES

Artigo Produção Nacional Revisado por pares

BIBTEX RIS

Formulations and an adaptive large neighborhood search for just-in-time scheduling of unrelated parallel machines with a common due window

2023; Elsevier BV; Volume: 153; Linguagem: Inglês

10.1016/j.cor.2023.106159

1873-765X

Gustavo Alencar Rolim, Marcelo Seido Nagano, Bruno de Athayde Prata,

Vehicle Routing Optimization Methods

In this paper, we address an unrelated parallel machine scheduling problem inspired by aspects of semiconductor manufacturing and other production systems. The objective is to minimize the total sum of weighted earliness and tardiness penalties when jobs are subject to a common restrictive due window. We conceptualize the problem, present two mixed-integer linear programming (MILP) formulations, and give necessary but not sufficient conditions for an optimal schedule. Since optimal schedules do not necessarily start at time zero, we derive two constructive heuristics coupled with a shift-forward procedure that determines leading idle times based on the elimination of straddling jobs. We propose a novel earliness–tardiness extension of the adaptive large neighborhood search (ET-ALNS) with several ad hoc removal/insertion operators and an embedded procedure to accelerate the calculation of the objective function. We carry out extensive computational experiments on a new set of 600 benchmark instances and compare our methods against two modern solvers with an incorporated warm-start mechanism as well as other state-of-the-art algorithms designed for closely related problems. A careful statistical analysis is conducted and results show that ET-ALNS outperforms the remaining methods by a significant margin.