Theoretical framework for formulating MIP scheduling models with multiple and non-uniform discrete-time grids

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We present a framework for the formulation of MIP scheduling models based on multiple and nonuniform discrete time grids. In a previous work we showed that it is possible to use different (possibly non-uniform) time grids for each task, unit, and material. Here, we generalize these ideas to account for general resources, and a range of processing characteristics such as limited intermediate storage and changeovers. Each resource has its own grid based on resource consumption and availability allowing resource constraints to be modeled more accurately without increasing the number of binary variables. We develop algorithms to define the unit-, task-, material-, and resource-specific grids directly from problem data. Importantly, we prove that the multi-grid formulation is able to find a schedule with the same optimal objective as the discrete-time single-grid model with an arbitrarily fine grid. The proposed framework leads to the formulation of models with reduced number of binary variables and constraints, which are able to find good solutions faster than existing models.

Original languageEnglish (US)
Pages (from-to)233-254
Number of pages22
JournalComputers and Chemical Engineering
Volume72
DOIs
StatePublished - Jan 2 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Chemical Engineering(all)
  • Computer Science Applications

Keywords

  • Mixed-integer programming
  • Process optimization
  • Supply chain management

Fingerprint Dive into the research topics of 'Theoretical framework for formulating MIP scheduling models with multiple and non-uniform discrete-time grids'. Together they form a unique fingerprint.

Cite this