(582a) A Novel Mixed-Time Mip Scheduling Model for Supply Chain Optimization

The purpose of the paper is to present a MIP model that can be readily used for the simultaneous optimization of scheduling and supply chain management (SCM) problems. A number of issues that are usually neglected in standalone scheduling models become important when scheduling is integrated with supply chain optimization:

· Smooth demand patterns at the customer-facing nodes are transformed into peaks of demand at the production facilities, due to the inventory policy applied at the intermediate nodes to account for demand uncertainty.

· Demand cannot always be satisfied on time and backlog costs are introduced to account for unmet demand; holding and backlog costs are important, especially at the intermediate nodes of the supply chain.

· Shipments are usually made at fixed time intervals (e.g. at the end of each week). This implies that scheduling models have to handle multiple fixed release and due dates at low computational cost.

· Features such as seasonality of demand, and scheduled maintenance and shut-downs require long planning horizons, and the trade-off between changeover and holding costs (i.e. lot-sizing) is crucial.

To account for scheduling decisions when we optimize the supply chain of process industries, therefore, current scheduling models should be amended to simultaneously handle lot-sizing, holding, backlog, changeover and shipment costs and multiple intermediate release and due dates, while solution methods should be enhanced to effectively solve problems over long time horizons.

BACKGROUND

The State Task Network (STN) formulation [1] and the Resource Task Network (RTN) formulation [2] are two powerful modeling tools that have been refined by several researchers [3-10] and extensively used for planning and scheduling problems. In discrete-time STN/RTN models the time horizon is divided into N periods (intervals) of equal duration, common for all units, and tasks begin and finish exactly at a time point. The advantage of these models is that holding and backlog costs are linear, and that release and due dates are handled at no additional costs. Their disadvantage is that variable processing times are modeled as discrete approximations using additional binary variables. In continuous-time models the time horizon is divided into time periods of unequal and unknown duration. Continuous-time models account for variable processing times, but since the time points are not fixed, holding and backlog costs cannot be calculated linearly, due dates are very expensive to model, and the number of intervals needed to accurately represent the optimal solution is unknown. Therefore, to solve problems where the objective is the minimization of total cost (i.e. holding+backlog+changeover costs) with intermediate release and due dates and variable processing times, features of both representations are needed.

PROPOSED MODEL

In this paper we propose an STN-based model with a mixed-time representation: the time grid is fixed, but we allow tasks to have variable batch-size and processing time. Hence, a task is forced to start exactly at a time point but it is allowed to span an unknown number of time periods and finish anywhere within a time period. For the timing of tasks we use the time matching constraints of Sundaramoorthy and Karimi [10]. The proposed model may yield slightly suboptimal solutions because tasks are not forced to finish exactly at a time point, but it exhibits a number of modeling advantages:

1. Compared to continuous-time models, it accounts linearly for holding and backlog costs.

2. Compared to continuous-time models, it does not require additional binary variables for the modeling of release and due dates.

3. Compared to discrete-time models, it does not require additional binary variables for the modeling of tasks with variable processing times.

The proposed model can be readily extended to handle continuous processes as well as special features, such as changeover times and costs, shared storage tanks and utility constraints.

COMPUTATIONAL IMPROVEMENTS

To avoid long idle times, we often divide the time horizon in a large number of time periods, which leads to large MIP models. The fact that the time grid is fixed, however, allows us to develop a number of computational improvements:

1. Based on the minimum and maximum processing times we can calculate the minimum and maximum number of time intervals a task can last. This enables us to add tightening constraints for the assignment of tasks to units that connect the ?starting? binaries with the ?finishing? binaries.

2. We can also add tightening constraints that connect the duration of a task with the ?starting? binaries, as well as tighten the time-matching constraints proposed by Sundaramoorthy and Karimi [10].

3. Finally, we can develop valid inequalities for the remaining processing time at a time point of the fixed time grid, as well as valid inequalities that connect the batch-size of a task and the ?starting? binaries.

Note that similar computational improvements are not possible in continuous-time models.

The addition of constraints (1) reduces the integrality gap by 25-35%, while the addition of constraints (2) reduces the integrality gap by an additional 10-15%. Valid inequalities (3) do not yield substantial improvements when added at the root node because the time needed to solve each node also increases. Hence, we present a branch-and-cut algorithm where only violated constraints (3) are added. The branch-and-cut algorithm based on the strong MIP reformulation of the proposed model is more than one order of magnitude faster than the original mixed-time MIP model.

APPLICATIONS

Three examples are presented. The first example is a batch plant with both fixed and variable processing times. It is solved using various time grids (0.25 ? 1 hr). When the objective function is the maximization of production with no intermediate due dates continuous-time models are more effective. In the presence of intermediate due dates, however, the proposed model is superior. It is computationally cheaper and it yields a better solution than the continuous-time model of Maravelias and Grossmann [9].

The second example is a continuous plant with five equipment units in three stages, eleven states, and sixteen continuous tasks. The objective is the minimization of holding and backlog cost over a scheduling horizon of two weeks, with due dates at the end of each week. Unmet demand is backlogged; backlogged demand can be shipped only at the end of each day. Three different instances are solved with time grids varying between 24 and 2.4 hours. The optimal solution is obtained in all cases in less than 600 CPU seconds.

The third example is a continuous process with changeover costs. As expected, the introduction of changeovers makes the problem more difficult. Nevertheless, the optimal solution to a problem with sixteen tasks over a time horizon of two weeks is found in 240 CPU seconds when a time period of 12 hours is used, while a very good solution is obtained in 600 CPU seconds when a time period of 6 hours is used.

CONCLUSIONS

A novel mixed-time representation and two MIP formulations for the scheduling of batch and continuous processes are presented. It is shown that the proposed models yield very good solutions to problems that are difficult to address with existing methods. The advantage of the proposed approach is that it can be integrated with planning and supply chain optimization models because it accounts linearly for holding and backlog costs, it handles intermediate release and due dates at no additional computational costs and it accounts for variable processing times.

REFERENCES

1. Kondili, E.; Pantelides, C. C.; Sargent, R. A General Algorithm for Short-Term Scheduling of Batch Operations ? I. MILP Formulation. Comput. Chem. Eng. 1993, 17, 211-227.

2. Pantelides, C. C. Unified Frameworks for the Optimal Process Planning and Scheduling. Proceedings on the Second Conference on Foundations of Computer Aided Operations. 1994, 253-274.

3. Shah, N.; E.; Pantelides, C. C.; Sargent, R. A General Algorithm for Short-Term Scheduling of Batch Operations ? IÉ. Computational Issues. Comput. Chem. Eng. 1993, 17, 229-244.

4. Schilling, G.; Pantelides, C. C. A Simple Continuous-Time Process Scheduling Formulation and a Novel Solution Algorithm. Comput. Chem. Eng. 1996, 20, S1221-1226.

5. Ierapetritou, M. G.; Floudas, C. A. Effective Continuous-Time Formulation for Short-Term Scheduling. 1. Multipurpose Batch Processes. Ind. Eng. Chem. Res. 1998, 37, 4341-4359.

6. Mockus, L.; Reklaitis, G.V. Continuous Time Representation Approach to Batch and Continuous Process Scheduling. 1. MINLP Formulation. Ind. Eng. Chem. Res. 1999, 38, 197-203.

7. Castro, P.; Barbosa-Povoa, A. P. F. D.; Matos, H. An Improved RTN Continuous-Time Formulation for the Short-term Scheduling of Multipurpose Batch Plants. Ind. Eng. Chem. Res. 2001, 40, 2059-2068.

8. Lee, K.; Il Park, H.; In Beum Lee. A Novel Nonuniform Discrete Time Formulation for Short-Term Scheduling of Batch and Continuous Processes. Ind. Eng. Chem. Res. 2001, 40, 4902-4911.

9. Maravelias, C.T.; Grossmann, I.E. A New General Continuous-Time State Task Network Formulation for the Short-Term Scheduling of Multipurpose Batch Plants. Ind. Eng. Chem. Res., 2003, 42(13), 3056-3074.

10. Sundaramoorthy, A.; Karimi, I.A. A Simpler Better Slot-based Continuous-time Formulation for Short-term Scheduling in Multipurpose Batch Plants. Chem. Eng. Sci., 2005, 60(10), 2679-2702.