A novel exact formulation for parallel machine scheduling problems

Luana M. Carrilho, Fabricio Oliveira*, Silvio Hamacher

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

18 Downloads (Pure)

Abstract

Machine scheduling is one of the most studied problems due to its technical challenges and prevalence in real life. In the literature, continuous- and discrete-time formulations are the two most known formulations for scheduling problems. However, continuous-time formulations often suffer from weak linear relaxations, while discrete-time formulations struggle with large numbers of variables. In contrast, the bucket-indexed formulation is an alternative that mitigates both issues by working with partial time discretization. We propose a mixed-integer linear programming model based on a bucket-indexed formulation to solve a nonpreemptive scheduling problem of identical parallel machines considering release dates, deadlines, precedence, eligibility, and machine availability constraints. We evaluate the proposed formulation against real-world instances comprising more than 400 jobs and 100 machines, comparing its performance against equivalent continuous- and discrete-time formulations. Remarkably, our formulation can be solved to optimality for all instances, outperforming both continuous- and discrete-time formulations.

Original languageEnglish
Article number108649
Pages (from-to)1-11
Number of pages11
JournalComputers and Chemical Engineering
Volume184
DOIs
Publication statusPublished - May 2024
MoE publication typeA1 Journal article-refereed

Keywords

  • Bucket-indexed formulation
  • MILP formulation
  • Scheduling

Fingerprint

Dive into the research topics of 'A novel exact formulation for parallel machine scheduling problems'. Together they form a unique fingerprint.

Cite this