EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2392. Arc Flow Formulation for the Robust Parallel Machine Scheduling Problem

Invited abstract in session WD-49: Mathematical programming for machine scheduling, stream Lot Sizing, Lot Scheduling and Production Planning.

Wednesday, 14:30-16:00
Room: M1 (building: 101)

Authors (first author is the speaker)

1. Heloisa Vasques da Silva
FEB, São Paulo State University (UNESP)
2. Alberto Locatelli
Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia
3. Silvio Alexandre de Araujo
Departamento de Matemática, Universidade Estadual Paulista-UNESP
4. Manuel Iori
DISMI, University of Modena and Reggio Emilia

Abstract

In the Parallel Machine Scheduling Problem (PMS) with makespan minimization, we are given a set of jobs with processing times and a set of identical parallel machines. Each machine processes at most one job at a time, and preemption is not allowed. The problem consists of scheduling all jobs into the machines, minimizing the maximum completion time of the jobs. Considering the fact that the processing times of the jobs are not exactly known in advance but typically belong to a given interval, in this work, we address a variant of the PMS designed to represent data uncertainties affecting the processing times. The resulting Robust Parallel Machine Scheduling Problem (RPMS) uses a budgeted uncertainty set, where a limit is imposed on the number of jobs whose processing time can change from their nominal value on each machine. Starting from the Dynamic Programming (DP) algorithm for the 0-1 Robust Knapsack Problem, we introduce an arc flow formulation based on the DP algorithm. To assess the efficiency of the model, we have tested it on a set of instances from the literature, identifying the methods that yield the best results.

Keywords

Status: accepted

Back to the list of papers