Combinatorial Optimization & Graph Algorithms

Algorithms for Scheduling Scarce Resources in Chemical Engineering

Participants:	Andreas Fest Rolf H. Möhring Frederik Stork Marc Uetz
Cooperation with:	Zentalbereich Informatik und Kommunikationstechnik, Systeme für die Chemie
Supported by:	within the research program Mathematical Methods for Solving Problems in Industry and Business

Project description:
Facing the increasing international competition, there is a growing need for planning tools in chemical engineering that allow an efficient utilization of scarce resources. Within the cooperation with BASF AG, we focus on a scheduling problem that is typical for the chemical industry, but also occurs in many other industrial applications. The aim is to schedule the production process for several so-called orders, such that the overall production time is minimized and the production facilities are properly used: The orders need to be allocated to individual machines, which in turn have to be operated by correspondingly skilled personnel.

The production process for each order consists of a sequence of identical jobs, each of which must be scheduled without interruption on the assigned machine. Due dates for individual orders are given, and there may also be precedence constraints between jobs of different orders, for instance if an intermediate product of an order is needed within the production process of others, or if certain production steps need to be synchronized.

Additionally, there are temporal restrictions of a more technical nature. To give an example, consider an intermediate product that has to cool down before processing can be continued, but processing must start before the impact of undesired side effects becomes too large. Due to such time sensitive effects, one of the peculiarities within chemical production processes is the presence of minimal as well as maximal time lags, so-called time windows.

Apart from that, resource constraints are imposed by limited availability of machines and scarce personnel (the availability of personnel depends on shifts, breaks, holiday, etc.). A job itself consists of several consecutive tasks, and each of these tasks requires a specified amount of personnel. Thus, the personnel requirement of any job is varying in time, and given by a corresponding piecewise constant function.

In this project the aim is to provide an interactive tool for short- and long-term planning that delivers optimal, or at least provably good solutions. This shall be achieved by exploiting new developments and insights from combinatorial optimization. Among others, these are:

• A tailor made branch and bound approach for scheduling problems with time windows,
• linear programming and Lagrangian relaxations in order to obtain strong lower bounds,
• approximation algorithms for machine scheduling problems for the design of powerful heuristics,
• an order theoretic approach to scheduling problems via insights about the interval order polytope.

The core problem within the scheduling process is - in mathematical terms - a resource-constrained project scheduling problem with time windows (generalized precedence constraints). For this problem, we have implemented a branch-and-bound algorithm which is originally based on the paper by Bartusch, Möhring, and Radermacher (Scheduling project networks with resource constraints and time windows, Annals of Operations Research 16 (1988) pp. 201-240). However, we have developed a new concept which, although based on the same principles, has completely different ingredients. With this implementation we were able to achieve very promising results for real-world instances from BASF AG.

The production schedule for a typical application.

Apart from the branch-and bound algorithm, we have developed and implemented a new procedure to compute strong lower bounds in very reasonable time. Lower bounds are particularly important to judge the quality of solutions if the optimum is not known. The approach relies on a Lagrangian relaxation of the resource constraints which results into a scheduling problem with start time dependent costs. Such problems can be reduced to a minimum cut computation in an appropriately defined digraph and can therefore be solved efficiently. Armed with these theoretical insights, we have implemented a subgradient optimization procedure to compute lower bounds on the makespan (or other objectives) for resource-constrained project scheduling. At its core, in each iteration a minimum cut is computed by a push-relabel maximum-flow algorithm. This approach turns out to have an excellent tradeoff between computation times and quality of the bounds computed.

In addition, we have integrated a heuristic component to the subgradient optimization procedure. The resulting algorithm is capable of computing both lower bounds as well as feasible solutions at the same time. The heuristic procedure makes use of list scheduling algorithms combined with ideas from the design of approximation algorithms in machine scheduling. The quality of the solutions we obtain by this approach compares to state-of-the-art heuristic (local search) algorithms. The solutions, particularly the quality of the lower bounds, can be iteratively improved by allowing more computation time. Most important, however, is that the approach provides powerful lower and upper bounds at the same time. Compared to purely primal heuristics which rely on the critical path lower bound only, the deviation between lower and upper bounds can thus be drastically reduced.

Iterative improvement of lower and upper bounds. See a movie (animated gif, 1 MB).

Apart from that, a completely different, order theoretic approach to the problem is currently being considered. It is based on the idea that every schedule induces an interval order and vice versa. Within this approach we utilize the branch and cut software package ABACUS from the University of Cologne, and try to take advantage of the knowledge about cutting planes for the interval order polytope. The goal is to find good feasible schedules via corresponding interval orders.

References:

• Scheduling Scarce Resources in Chemical Engineering, Rolf H. Möhring and Marc Uetz. This is the final report which summarizes some of the outcomes of this research project on a rather informal basis.
• Solving Project Scheduling Problems by Minimum Cut Computations, Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz. This is a journal version which combines and extends the two earlier reports 661 and 620. Submitted.
• A Note on Scheduling Problems with Irregular Starting Time Costs, Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz. Submitted.
• Resource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutions (4-page abstract), Frederik Stork and Marc Uetz. To appear in the Proceedings of the 7th International Workshop on Project Management and Scheduling.
• Resource-Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems, Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz. Extended abstract in: Algorithms - ESA '99, Jaroslav Nesetril (ed.), Lecture Notes in Computer Science 1643, Springer, Berlin, 1999, pp. 139-150, Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99).
• Resource-Constrained Project Scheduling with Time Windows: A Branching Scheme Based on Dynamic Release Dates, Andreas Fest, Rolf H. Möhring, Frederik Stork, and Marc Uetz. Submitted.
• P. Brucker, A. Drexl, R. H. Möhring, K. Neumann, and E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research 112 (1999), pp. 3-41.