(200f) From Time Representations In Scheduling to Hybrid Spatial Representations In 2-D Allocation Problems

There have been remarkable advances in scheduling approaches by the Process Systems Engineering community in the last 20 years. Major breakthroughs were: (i) unified frameworks for process representation that allow the systematic modeling of a process flowsheet or production recipe in terms of the virtual entities that are the state, tasks and resources; (ii) alternative time representations ranging from discrete-time to continuous-time, where a few alternative concepts can be employed (e.g. single time grid, multiple time grids, a.k.a. unit-specific, and immediate or general precedence sequencing variables).

In the context on N-dimensional allocation problems [1], scheduling problems can be viewed as being 1-D, in which the relevant dimension is time. Cutting and packing start at 2-D and one common aspect is that small items have to be packed into, or cut from, one or more objects, often called strips or bins. In the paper industry for example, the objective is cutting jumbo reels of paper into smaller reels so as to minimize trim losses.

Existing MILP models for 2-D allocation problems (e.g. strip packing) rely on a full continuous-space representation featuring continuous variables to determine the (x,y) coordinates of a given point of the rectangle in the strip [2-3]. The binary variables identify the relative position of a rectangle with respect to another and appear in the big-M, no overlap constraints. It is also straightforward to come up with a full discrete-space model using a mesh consisting of a 1x1 squares [4].

The novelty of this paper consists of two new MILP models that combine alternative spatial representation concepts into the x and y axis of the 2-D problem. It can be viewed as the follow-up of last year’s presentation that involved a discrete-space representation in the x-axis and a continuous-space representation with multiple time grids in the y-axis [4]. Now, we propose using sequencing variables in the y-axis whereas for the x-axis we can either use: (i) a discrete-space representation or (ii) a continuous-space representation with a single grid [5]. Note that while the former can be classified as a hybrid discrete/continuous-space model, the latter is a full continuous-space model.

The computational performance has been tested in a set of 29 test instances taken from the literature including some of the well-known cgcut, ngcut and ht instances. Interestingly all 5 MILPs tested (one discrete-space, two hybrid discrete/continuous and two continuous-space models) are valid approaches in the sense that they are the best approach for at least one problem. Some require specialized solution strategies in the search for the global optimal solution (e.g. when using spatial grids consisting of multiple event points, a problem inherited from their scheduling counterparts) while for others solving the model just once is enough.

[1] Westerlund J, Papageorgiou LG, Westerlund T. A MILP model for N-dimensional allocation. Comput. Chem. Eng. 2007; 31: 1702-1714.

[2] Castillo I, Westerlund J, Emet S, Westerlund T. Optimization of block layout design problems with unequal areas: A comparison of MILP and MINLP optimization models. Comput. Chem. Eng. 2005; 30: 54-69.

[3] Sawaya NW, Grossmann IE. A Cutting Plane Method for Solving Linear Generalized Disjunctive Programming Problems. Comput. Chem. Eng. 2005; 29: 1891-1913.

[4] Castro PM, Oliveira JF. Scheduling Inspired Models for Two-Dimensional Packing Problems. European Journal of Operational Research. Under Review.

[5] Castro PM, Barbosa-Póvoa AP, Matos HA,; Novais AQ. Simple Continuous-Time Formulation for Short-Term Scheduling of Batch and Continuous Processes. Ind. Eng. Chem. Res. 2004; 43: 105-118.