(723b) Multiple Time Grids in Discrete-Time Models for Scheduling and Supply Chain Planning

Sara Zenner, Kaushik Subramanian, and Christos T. Maravelias

Department of Chemical and Biological Engineering, University of Wisconsin – Madison

1415 Engineering Dr., Madison, WI 53706, USA

The modeling of time plays a key role in the formulation of mixed-integer programming (MIP) models for scheduling, production planning, and operational supply chain planning problems. It affects the size of the model, the computational requirements, and the quality of the solution. While many types of time grids have been proposed in the literature for continuous-time models, discrete-time models have always been thought of as having a single grid with equally spaced time points. However, the ability to incorporate different grids into a single model is useful in many situations. For example, processes in different facilities that interact with each other may use different grids. Also, tasks in the same facility (executed on the same or different units) may have very different processing times. Finally, externally imposed events, such as due times or raw material deliveries, may not occur at a point of the grid used to represent the processing tasks.

To model all the aforementioned situations, existing approaches either introduce approximations or employ a very fine grid, typically based on the largest common factor among all time scales of interest, for the entire scheduling/planning horizon. Unfortunately, having a large number of time points leads to models that may be too large to solve in a reasonable time.

We present methods to formulate discrete-time multi-grid models that allow different tasks, units, or materials to have their own time grid. The length of the planning periods of the grids do not have to be multiples of the same factor. In addition, each grid may have periods of (known but) unequal length. Since a discrete-time approach is used, the multiple time grids are easily “synchronized” because all time points are known beforehand. The proposed methods lead to substantial reductions in the size of the formulations and thus the computational requirements. In addition, they can yield better solutions than formulations that use approximations. Finally, we show how to carefully select the different time grids, so that we obtain solutions that are comparable with the ones obtained using a single fine grid to represent the processing of all tasks and occurrence of events.