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  
email: moehring[at]math.tuberlin.de  
Researchers:  Dr. Nicole Megow  
Jens Schulz  
emails: {nmegow, jschulz}[at]math.tuberlin.de  
For address, see above.  
Cooperation partners: 

Problem Description
In chemical manufacturing and petroleum refining, largescale 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 outofservice cost. Therefore a good schedule for the turnaround is of high priority to the manufacturer.
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 TimeCost 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 TimeCost Tradeoff problem. It is known to be NPhard[2] and approximation algorithms have been investigated; see Skutella[3]. In case that cost functions are continuous linear functions, the TimeCost 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 timecost 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 TimeCost 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 twophase approach to solve this problem. In the first step we compute the so called timecost tradeoffcurve 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.
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 copartner 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 26, 2007. 
[2] 
P. De, E.J. Dunne, J.B. Ghosh, and C.E. Wells. The discrete timecost tradeoff problem revisited. European Journal of Operational Research, 81:225238, 1995. 
[3] 
M. Skutella. Approximation Algorithms for the Discrete TimeCost Tradeoff Problem. Mathematics of Operations Research, 23(4):900929, 1998. 
[4] 
D.R. Fulkerson. A network flow computation for project cost curves. Management Science, 7:167178, 1961.t 
[5] 
J.E. Kelley. CriticalPath planning and scheduling: Mathematical basis. Operations Research, 9(3):296320, 1961. 
[6] 
S. Phillips and M. I. Dessouky. Solving the project time/cost tradeoff problem using the minimal cut concept. Management Science, 24:393400, 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):613627, 2002. 
[8] 
K. Jansen and H. Zhang. An approximation algorithm for scheduling malleable tasks under general precedence constraints. ACM Transactions on Algorithms, 2(3):416434, 2006. 
[9] 
I. Meilijson and A. Nadas. Convex majorization with an application to the length of critical paths. Journal of Applied Probability, 16:671677, 1979. 
[10] 
G. Weiss. Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and reliability. Operations Research, 34:595605, 1986. 
Master theses.
[M1] 
Jens Schulz ZeitKostenOptimierung im Shutdown / Turnaround Scheduling Diploma thesis at TU Berlin, Institute of Mathematics at coga group , Berlin, 2007. 
[M2] 
Michael Krätsch Ressourcenausgleich bei SchedulingProblemen 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 26, 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 BranchandPrice 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 26, 2007. 
[P2] 
Nicole Megow, Rolf H. Möhring,
and Jens Schulz Decision Support and Optimization in Shutdown and Turnaround Scheduling TechReport 0092009. 