On the combinatorial structure of discrete-time MIP formulations for chemical production scheduling

We study the structure of discrete-time mixed-integer programming (MIP) models for chemical production scheduling. We discuss how chemical manufacturing facilities can be represented as dynamic networks and then converted into time-expanded networks with side constraints. Based on this representation, we show that material balance constraints of the MIP models correspond to generalized flow balances in time-expanded networks. We discuss the implications of conversion coefficients in tasks with multiple inputs and outputs. We also show that assignment constraints lead to side constraints that are equivalent to clique constraints in the time-expanded task-graph of the facility. Finally, we discuss how variable batchsizes lead to fixed charge network structures.

► We study the structure of discrete-time state-task network mixed-integer programming (MIP) models for chemical production scheduling.
► We show that scheduling models combine structures of well known combinatorial optimization problems.
► Our results suggest that integrating known solution methods can potentially lead to effective MIP algorithms.