Scheduling entails task planning (to meet specific goals) under resource constraints (material and human), time and workflow constraints (processes). This is a familiar problem in Optimization, and its exact resolution (i.e. finding the optimal) takes time that increases exponentially with the size of the problem to address (what is known as a NP-Complete problem, where “NP” stands for “Non Polynomial” and thus exponential).
In industry the sheer scales involved are large (sprawling factories, high volumes/daily issues), if not massive (because if one is going to invest in a software package, it should be able to compute at least several weeks’ work in progress). Response times of several minutes, if not hours can be achieved with solutions that use the exact optimal approach. Clients increasingly clamor for real-time results, i.e., solutions that need to be recalculated whenever a contingency is detected. The resulting computing times for these optimal modules are incompatible with real-time use.
In the past, these issues were dealt with using mathematical programming (PL/MIP or PPC), which suffer from combinatorial explosion due to the discrete aspect of the problem (disjunctive constraints). To reduce the response time, the search for solutions can be restricted, but even with very targeted strategies for a given business, the algorithms used by the solvers that guarantee accuracy (and thus response optimality) use too much processing time. Not only that, but in the event of frequent and/or sizeable contingencies, an optimal situation at instant T will soon be obsolete, if not unsafe if it implies unfeasible times (because of the constant onslaught of contingencies).
Scheduling entails task planning (to meet specific goals) under resource constraints (material and human), time and workflow constraints (processes). This is a familiar problem in Optimization, and its exact resolution (i.e. finding the optimal) takes time that increases exponentially with the size of the problem to address (what is known as a NP-Complete problem, where “NP” stands for “Non Polynomial” and thus exponential).
In industry the sheer scales involved are large (sprawling factories, high volumes/daily issues), if not massive (because if one is going to invest in a software package, it should be able to compute at least several weeks’ work in progress). Response times of several minutes, if not hours can be achieved with solutions that use the exact optimal approach. Clients increasingly clamor for real-time results, i.e., solutions that need to be recalculated whenever a contingency is detected. The resulting computing times for these optimal modules are incompatible with real-time use.
In the past, these issues were dealt with using mathematical programming (PL/MIP or PPC), which suffer from combinatorial explosion due to the discrete aspect of the problem (disjunctive constraints). To reduce the response time, the search for solutions can be restricted, but even with very targeted strategies for a given business, the algorithms used by the solvers that guarantee accuracy (and thus response optimality) use too much processing time. Not only that, but in the event of frequent and/or sizeable contingencies, an optimal situation at instant T will soon be obsolete, if not unsafe if it implies unfeasible times (because of the constant onslaught of contingencies).