A mathematical programming model for minimizing the number of tardy jobs in parallel machines subject to availability constraints

Parallel machine scheduling consists of assigning a set of activities to a work schedule such that they do not overlap aiming at finding a schedule that optimizes a certain performance measure. In this work, a particular case of the parallel machine scheduling problems is considered, where the goal is to minimize the number of tardy jobs subject to machine availability constraints, such that the demand at the Automation Center of the Pontificia Universidad Javeriana can be satisfied before the deadlines. A mathematical model is adapted to consider both unavailability restrictions and to allow Non- Preemptive Scheduling of activities that can be finished before the beginning of the next time interval during which the machine is available. Moreover, an extension for a state-of-the-art heuristic approach is evaluated to propose an efficient strategy to provide near-optimal scheduling that properly works in practice, particularly for contexts where the budget to access cutting-edge optimization software is scarce and the availability constraints are not considered. The proposed algorithms are compared through a large testbed of simulated instances demonstrating that both may be strong and computationally efficient when faced with realistic settings, and the problem stated at the Automation Center is solved.

La schedulazione di macchine parallele consiste nell'assegnare un insieme di attività a una programmazione in modo che non si sovrappongano, con l'obiettivo di trovare un programma che ottimizzi una determinata misura delle prestazioni. In questo documento, è considerato un caso particolare di problemi di programmazione di macchine parallele, in cui l'obiettivo è quello di ridurre al minimo il numero di lavori tardivi soggetti a vincoli di disponibilità della macchina, tale che la domanda presso il Centro di automazione della Pontificia Universidad Javeriana possa essere soddisfatta prima della scadenze. Un modello matematico è adattato sia per considerare i vincoli di non disponibilità sia per consentire la programmazione non preventiva di attività che possono essere completate prima dell'inizio del successivo intervallo di tempo durante il quale la macchina è disponibile. Inoltre, si valuta un'estensione di un approccio euristico allo stato dell'arte per proporre una strategia efficiente per fornire una programmazione quasi ottimale che funzioni correttamente nella pratica, in particolare in contesti in cui il budget per accedere al software di ottimizzazione all'avanguardia è scarso e i limiti di disponibilità non vengono presi in considerazione. Gli algoritmi proposti sono confrontati attraverso un ampio banco di prove simulate che dimostrano che entrambi possono essere forti e computazionalmente efficienti di fronte a configurazioni realistiche, e il problema dichiarato nel Centro di automazione è risolto.