59th Annual Report on Research 2014

To effectively address rescheduling, effective solution methods for general mixed-integer programming (MIP) scheduling models are needed. While the Process Systems Engineering (PSE) community has traditionally focused its research efforts on developing different modeling strategies, recent studies have shown that in order to solve instances of industrial relevance, the development of systematic solution strategies is as relevant as the formulation of robust models. Thus, to address rescheduling, we have focused our initial efforts towards the development of preprocessing and tightening methods that will enable us to solve MIP scheduling models of industrial relevance within a time frame suitable for online scheduling. Specifically, we have been working towards the development of an algorithm to improve the computational efficiency of problems in which the objective function is the maximization of profit, sales, or total production.

We are developing a propagation algorithm based on time and inventory considerations that preprocess the data information and automatically generates valid inequalities that tighten the original discrete- and continuous- time formulations (Merchan and Maravelias, in preparation). A summary of the main procedures we have developed for the construction of the proposed algorithm is given next.

1. Definition of time windows () for each task-unit assignment through calculation of earliest starting time () and shortest tail () parameters that use information for processing time and unit capacity as well as propagation of the material availability and inventories.
2. Calculation of the maximum allowable amount each task () and material () can reach within the given horizon, using the time windows generated in step 1.
3. Definition of dependency groups for tasks for which the allowable number of batches leads to linear combinations rather than single upper bounds. These subgroups of tasks are automatically identified by tracking shared upstream units and/or materials.
4. Computation and propagation of linear combination coefficients for the subgroups identified in step 3. Once the maximum number of batches for each task in the subgroup has been determined, constraints are generated by calculating the convex hull of the set of feasible integer points that represent allowable combinations of batches within the subgroup. This information is propagated downstream to be taken into account by subsequent subgroups.
5. Additional constraint propagation can be introduced if the earliest star time and shortest tail are required to be variables with upper bounds defined by the parameters calculated in step 1. In this case, tightenimg constraints can be developed and propagated to downstream tasks and units.

We are currently working on the integration of these five steps to produce the tightest version of the valid inequalities by analyzing the interactions between different sets of constraints. We expect to submit a paper discussing these methods within the next two months.