(79e) Scheduling Algorithm for Large Scale Multiproduct Plants

The increasingly large literature in the scheduling field highlights the successful application of optimization approaches to a wide variety of challenging problems (Méndez et al., CCE 2006, 30, 913). This important achievement comes from the remarkable advances in modeling techniques, algorithmic methods and computational technologies that have been made in the last decade or so. However, there is still a significant gap between theory and practice. Academic developments are mostly tested on relatively small problems whereas real-world applications consist of hundreds of batches, dozens of pieces of equipment and long scheduling horizons.

In order to make exact methods mode attractive, efforts have been increasingly oriented towards the development of systematic techniques that allow maintaining the number of decisions at a reasonable level. Manageable model sizes may be obtained by applying heuristic model reduction methods, decomposition or aggregation techniques. Once an initial solution is generated, gradual improvement through optimization based methods can be obtained with modest computational effort. Although these can no longer guarantee optimality, this may not be critical in practice due to the following: (i) very short time is available to generate a solution; (ii) theoretical optimality easily gets lost due to the dynamic nature of industrial environments; (iii) implementing the schedule as such is often limited by the real process; (iv) only a subset of the actual scheduling goals are taken into account.

The purpose of this paper is to systematically address the short-term scheduling of multistage batch plants with parallel units following the decision, for each particular product, of the number and size of batches to produce; resulting in a set of orders with fixed processing times and release/due dates. A complex algorithm is proposed that can be parameterized for the fast and efficient solution of problems of varying size. The key idea is essentially the one proposed by Röslof et al. (CCE 2001, 25, 821) and further explored by Méndez and Cerdá (CCE 2003, 27, 1247). The complete set of orders is scheduled sequentially by considering one, or a couple of them, at a time. As we proceed through the iterations, previously scheduled orders can be partly rescheduled to allow for some flexibility while keeping the combinatorial complexity at a manageable level. Once a complete schedule is obtained, the same concept is applied to improve the schedule locally.

The novel aspects are: (i) the use of a multiple time grid continuous-time model instead of one based on sequencing variables; (ii) the decomposition strategy specifies on each iteration the minimum number of time slots in the grid for the unit-specific model, thus removing the uncertainty in the specification of this parameter; (iii) the introduction of an intermediate level of complexity between the full-space problem and the option of fixing both the order-unit assignments and relative ordering of previously scheduled orders.

The results show that the fixed relative ordering strategy is a better option than its free ordering counterpart, which has a high computational cost. It is able to generate good solutions very rapidly and we were able to tackle a real-life 50-order, 17-unit, 6-stage problem in less than a minute. In terms of the tradeoff between solution quality and total computational effort, the best option is to schedule two orders per iteration. Two alternative preordering heuristics were also evaluated leading to the conclusion that is better to use the minimum slack time (MST) rather than the earliest due date (EDD) heuristic for order-iteration assignment.