Infeasibility Analysis for Scheduling Applications

Planning and scheduling software are crucial for industries and must provide feasible, robust, and operationally acceptable schedules. Our focus in this presentation is on tactical scheduling with a horizon of hours or days where real-time disturbances need to be accommodated into any proposed schedule. Equipment failures, resource storage policy change, resource availability are examples of such real-world uncertainties and in many cases, the optimal schedule obtained a priori is not robust to such changes. On-the-fly rescheduling algorithms try to repair such infeasibilities by employing quick heuristics.

In this work, we present use of infeasibility analysis in the context of rescheduling for a multi-purpose chemical batch process. We identify irreducible inconsistent sets (IISs), which are subsets of an infeasible model, such that the IIS itself is infeasible but any proper subset of the IIS is feasible. We isolate multiple IISs systematically and identify bottle-necks in process scheduling network by discovering a set of mutual inconsistencies that must be eliminated to achieve feasibility. We demonstrate this approach through an interactive and intuitive scheduling interface for variety of scheduling models using the well-known Westernberger-Kallrath case study.