We propose a series of preprocessing algorithms for the generation of strong valid inequalities for time-indexed, discrete and continuous, mixed-integer programming scheduling models for problems in network production environments. Specifically, starting from time- and inventory-related instance data, the proposed algorithms use constraint propagation techniques to calculate parameters that are used to bound the number of times subsets of tasks can be executed in a feasible solution. We also extend some of the propagation ideas to generate three classes of new tightening constraints. The proposed methods result in tightening constraints expressed in terms of assignment binary variables (Xijt=1 if task i is assigned to start on unit j at time point t) which are present in all time-indexed MIP models, therefore they are applicable to all time-indexed models accounting for a wide range of processing features. Finally, the methods are shown to lead to up to two orders of magnitude reduction in computational time when optimal solutions are found and significantly improve optimality gap when a time limit is enforced.
All Science Journal Classification (ASJC) codes
- Chemical Engineering(all)
- Computer Science Applications
- Constraint propagation
- Strong valid inequalities