Shutdown and Turnaround Scheduling in Chemical Manufacturing

Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 24594
e-mail: moehring[at]math.tu-berlin.de
Researchers: Dr. Nicole Megow
Jens Schulz
emails: {nmegow, jschulz}[at]math.tu-berlin.de
For address, see above.
Cooperation partners:

Problem Description

In chemical manufacturing and petroleum refining, large-scale maintenance activities must be conducted on a regular basis. Entire production units are shut down for disassembly and comprehensive inspection and renewal. Such a process is called Shutdown and Turnaround (or turnaround for short). It is an essential process but causes high out-of-service cost. Therefore a good schedule for the turnaround is of high priority to the manufacturer.

Figure 1: cat-cracker
A cat cracker. A typical production unit in chemical engineering. © www.eia.doe.gov

In a turnaround a huge number of interdependent operations (jobs) must be executed by maintenance groups of different specializations (different resources). We suppose that each job is carried out by exactly one type of resource. Given a minimum and maximum number of resources we have to decide how many workers are executing a job. Each resource unit causes a certain cost for each time unit it is used. By increasing the number of resources the processing time decreases but the cost increase. Further more the number of resources is limited and working shifts have to be respected. The execution of a job may take longer due to unforseen events. Thus we are facing stochastic processing times.


A project manager needs decision support to choose a project duration according to the project cost and the associated risk. Having fixed a project duration, one is looking for a schedule with evenly used resources.

Related work

The turnaround scheduling problem can be interpreted as a generalization of the Time-Cost Tradeoff Problem and the problem of scheduling malleable jobs. In fact, relaxing the goal of leveling the resource usage for each type over the project duration leads to the Discrete Time-Cost Tradeoff problem. It is known to be NP-hard[2] and approximation algorithms have been investigated; see Skutella[3]. In case that cost functions are continuous linear functions, the Time-Cost Tradeoff Problem can be solved optimally by combinatorial algorithms as has been shown independently by Fulkerson[4] and Kelley[5]. Improved versions are given by Philips and Dessouky[6]. In these models due dates, resource capacities and working shifts are not considered.

The problem of scheduling malleable jobs can be seen as a step towards combining time-cost optimization with resource leveling. Here, resource capacities are predefined in the form of parallel machines. Precedence constraints are given and the duration of a job is determined by the number of machines on which it is processed. Recent work by Lepere et al.[7] and Jansen and Zhang[8] provide approximation algorithms with constant performance guarantees.

One question in turnaround scheduling addresses the uncertainty of a determined schedule. Here, techniques by Meilijson and Nadas[9] and Weiss[10] which are strongly related to the Linear Time-Cost Tradeoff Problem can be applied to determine an upper bound on the expected lateness for a given project schedule.

Solution procedure

Because of the stepwise decisions a project manager has to make we have implemented a two-phase approach to solve this problem. In the first step we compute the so called time-cost tradeoff-curve and confidence intervalls which tell for a chosen project duration with which probability which project duration can be kept.

In the second step having fixed a project duration we start a resource leveling procedure based on list scheduling and binary search. We are able to handle several side constraints such as release and due dates or jobs which have to be executed in parallel or are not allowed to be executed at the same time.

Figure 2: time-cost tradeoff-curve Figure 3: schedule
Time-Cost Tradeoff-curve and a leveled schedule with a specified resource profile.

Impact on industry

Our decision support tool has been succesfully integrated into SAP and MS Project Management software tools, as can be seen in this case study .

On the workshop Microsoft Office Enterprise Project Management Infotage 2009 held by our industrial co-partner of T.A. Cook, Tectura GmbH, the use of mathematical optimization tools in MS Project has been presented.


References.

[1] Nicole Megow, Rolf H. Möhring, and Jens Schulz
Turnaround Scheduling in Chemical Manufacturing [pdf]
Plenary talk at the 8th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2007), Istanbul, Turkey, July 2-6, 2007.
[2] P. De, E.J. Dunne, J.B. Ghosh, and C.E. Wells.
The discrete time-cost tradeoff problem revisited. European Journal of Operational Research, 81:225-238, 1995.
[3] M. Skutella.
Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem.
Mathematics of Operations Research, 23(4):900-929, 1998.
[4] D.R. Fulkerson.
A network flow computation for project cost curves.
Management Science, 7:167-178, 1961.t
[5] J.E. Kelley.
Critical-Path planning and scheduling: Mathematical basis.
Operations Research, 9(3):296-320, 1961.
[6] S. Phillips and M. I. Dessouky.
Solving the project time/cost tradeoff problem using the minimal cut concept.
Management Science, 24:393-400, 1977.
[7] R. Lepere, D. Trystram, and G.J. Woeginger.
Approximation algorithms for scheduling malleable tasks under precedence constraints.
International Journal of Foundations of Computer Science, 13(4):613-627, 2002.
[8] K. Jansen and H. Zhang.
An approximation algorithm for scheduling malleable tasks under general precedence constraints.
ACM Transactions on Algorithms, 2(3):416-434, 2006.
[9] I. Meilijson and A. Nadas.
Convex majorization with an application to the length of critical paths.
Journal of Applied Probability, 16:671-677, 1979.
[10] G. Weiss.
Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and reliability.
Operations Research, 34:595-605, 1986.

Master theses.

[M1] Jens Schulz
Zeit-Kosten-Optimierung im Shutdown / Turnaround Scheduling
Diploma thesis at TU Berlin, Institute of Mathematics at coga group , Berlin, 2007.
[M2] Michael Krätsch
Ressourcenausgleich bei Scheduling-Problemen mit variablen Vorgangsdauern und Schichtkalendern
Diploma thesis at TU Berlin, Institute of Mathematics at coga group , Berlin, 2008.
[M3] Elisabeth Günther
Bin Scheduling: Partitionieren verformbarer Jobs mit Nebenbedingungen
Diploma thesis at TU Berlin, Institute of Mathematics at coga group , Berlin, 2008.

Related Talks.

[T1] Nicole Megow, Rolf H. Möhring, and Jens Schulz
Turnaround Scheduling in Chemical Manufacturing [pdf]
Plenary talk at the 8th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2007), Istanbul, Turkey, July 2-6, 2007.
[T2] Nicole Megow, Rolf H. Möhring, and Jens Schulz
Turnaround Scheduling in Chemical Manufacturing [pdf]
Talk at the International Conference on Operations Research (OR 2007), Saarbrücken, Germany, 2007.
[T3] Marco Lübbecke, Rolf H. Möhring, and Jens Schulz
Branch-and-Price Algorithm for the Turnaround Scheduling Problem
Talk at the International Conference on Operations Research (OR 2008), Augsburg, Germany, 2008.

Publications.

[P1] Nicole Megow, Rolf H. Möhring, and Jens Schulz
Turnaround Scheduling in Chemical Manufacturing [pdf]
In Proceedings of 8th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2007), Istanbul, Turkey, July 2-6, 2007.
[P2] Nicole Megow, Rolf H. Möhring, and Jens Schulz
Decision Support and Optimization in Shutdown and Turnaround Scheduling
Tech-Report 009-2009.