zbMATH — the first resource for mathematics

Structured valid inequalities and separation in optimal scheduling of the resource-constrained batch chemical plant. (English) Zbl 0913.90169
Summary: Various structured valid inequalities for an existing mixed integer linear programming (MILP) batch process scheduling model are derived. The scheduling model handles a variety of complexities, including variable batch sizes, limited availability of resources, intermediate product draw-offs, and a number of objectives. The valid inequalities, whose validity is proven, are used to tighten the linear programming relaxation to the MILP scheduling formulation. Computational experiments were executed, and a separation algorithm was implemented. This algorithm detects violated valid inequalities and amends them to the original formulation. Although this separation algorithm is heuristic in nature, it performs quite well in practice. In order to exploit the new information at each node in the branch-and-bound tree, a simple heuristic algorithm that predicts which of the valid inequalities will be strong for the inner nodes is also discussed and its performance on various case studies is analyzed.

90B35 Deterministic scheduling theory in operations research