(696h) On the Solution of Time-Indexed Mixed-Integer Programming Scheduling Models

A general chemical production facility can be regarded as a series of tasks that transform a set of raw materials into finished goods, using limited resources (e.g. processing units, storage vessels, utilities, manpower). The scheduling problem in these facilities defines the sizing, assignment and timing of tasks, materials and available resources. A formal approach to its solution involves the mathematical formulation as a mixed-integer programming (MIP) problem. Unfortunately, these MIP models are very difficult to solve even for small- and medium-scale facilities; in fact, many industrial instances remain computationally intractable.

Several efforts have been made over the last two decades to enhance the solution process for MIP models. In particular, addition of valid inequalities has proved to greatly improve the computational performance of these formulations [1-3]. In this work, we introduce different families of tightening constraints based on preprocessing algorithms that use the input data for the problem, in particular customer demand and processing time.

The demand information is used to generate a back-propagation algorithm that calculates the minimum required amount of each material and the minimum amount that each task must produce in order to satisfy the final demand. Using this new information we are able to introduce two different types of tightening constraints: lower bound for the total number of batches produced by each task and lower bound in the total amount of material produced by each task. The proposed algorithm is able to handle both minimum batch size requirements for each unit and complex networks with recycle streams. It proves to be particularly useful to solve cost and makespan minimization problems.

Similarly, the processing time information induces a forward-propagation algorithm that determines both the maximum number of batches of a given task and the maximum amount of each material that can be produced within a given horizon. Thus, two different sets of upper-bounding constraints are introduced to tighten the original formulation. This algorithm can be extended to other types of objective functions; in particular, it can be applied to profit maximization since no demand information is required a priori. It is also suitable for complex networks and can be extended to handle variable processing times.

Moreover, the processing time data is also used within a third algorithm to determine the earliest starting time and the shortest tail time for both tasks and units, based on information for the minimum time to produce enough material to run a task and the task-unit pairing. Subsequently, additional constraints are introduced to bound the total processing time for a given task and the utilization time for a given unit in fixed-horizon problems and to lower bound the makespan variable in makespan minimization problems.

We test the proposed algorithms using a large pool of instances, that allows us studying the effect of different process networks, objective functions, problem features (e.g. variable processing times) and time representation. For the latter we provide an extensive comparison between different discrete-time and continuous-time models, making emphasis on the distinct modeling capabilities of each representation. The combined use of the algorithms and the refinements that can be introduced due to their interaction is also studied. Our methodologies can readily be extended to include the main features that appear in chemical production scheduling.

The main advantage of these algorithms is that they can be run offline in a few seconds since they only use the original problem data; the total solution time is practically not affected. By using the algorithms and constraints proposed in the present work we are able to (1) significantly increase the percentage of instances solved within an established time limit, (2) obtain order-of-magnitude reductions in computational time in comparison to the original formulations, and (3) decrease the optimality gap for instances that are not solved within the time limit.

References

[1] Velez, S.; Maravelias, C. T., Mixed-Integer Programming Model and Tightening Methods for Scheduling in General Chemical Production Environments. Industrial & Engineering Chemistry Research 2013, 52 (9), 3407-3423.

[2] Burkard, R. E.; Hatzl, J., Review, extensions and computational comparison of MILP formulations for scheduling of batch processes. Comput Chem Eng 2005, 29 (8), 1752-1769.

[3] Velez, S.; Sundaramoorthy, A.; Maravelias, C. T., Valid Inequalities Based on Demand Propagation for Chemical Production Scheduling MIP Models. Aiche Journal 2013, 59 (3), 872-887.