Theoretical framework for formulating MIP scheduling models with multiple and non-uniform discrete-time grids |
| |
Affiliation: | 1. Dan F. Smith Department of Chemical Engineering, Lamar University, Beaumont, TX 77710, USA;2. Department of Computer Science, Lamar University, Beaumont, TX 77710, USAn;1. Institute of Chemical Process Engineering, University of Alicante, Ap. Correos 99, Alicante 03080, Spain;2. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A.;1. Department of Dermatology, Kyoto University Graduate School of Medicine, Kyoto, Japan |
| |
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. |
| |
Keywords: | Mixed-integer programming Process optimization Supply chain management |
本文献已被 ScienceDirect 等数据库收录! |
|