DFG Project "Algorithms for Complex Scheduling Problems"
within DFG Priority Programme 1307 "Algorithm Engineering"

Turnaround Scheduling

A prototypical example of turnaround scheduling is the shut-down of a chemical plant for technical inspections, and, depending on that, for maintenance work and repairs. This type of problem contains very different algorithmical aspects:

  1. Finding the optimal execution time for the shut-down depending on the cost of a fast execution and the lost profit income during the shut-down period.
  2. Finding the optimal staff assignment taking into account upper bounds (scarce resources) and the possibility of decreasing the processing times of certain activities by increasing the staff assignment.
  3. Finding risk measures and policies to deal with unpredictable events (e.g. repairs that were not planned).

The goal is the development and testing of algorithms that solve the problems stated above. So far, only partial aspects of these problems have been studied, mostly in a theoretical context like approximation algorithms or online competitiveness.

Decision Support and Optimization.

For the discrete time-cost tradeoff problem with precedence constraints and time windows (first subproblem) and the resource leveling (second subproblem) an efficient two-phase approach was developed. See the website of the cooperation with T.A. Cook Consultants, Berlin for further description and motivation of the problem and [P8] for a detailed description of the approach.

In the first step of our two-phase approach we compute the so called time-cost tradeoff curve, which tells the user for each cost the best possible project duration, i.e. the makespan. In fact, the exact computation of this curve is not possible in an appropriate runtime. As a consequence, we compute a time-cost tradeoff curve which is based on a relaxation of the integrality of the work resources, leading to the classical time-cost tradeoff problem. See [1,3,5] for algorithms for this problem. The resulting curve yields a lower bound on the actual discrete time-cost tradeoff curve. In order to guarantee feasibility for each solution corresponding to a breakpoint in the curve, fractional resources are rounded up the next larger integer. By this method, the makespan might get much smaller than the actually chosen one, causing unreasonable high cost. To avoid this problem we try to decrease the used resources by a greedy method. We use a list-scheduling approach to ensure that also resource capacities and time windows are respected. Finally, we obtain a heuristic time-cost tradeoff curve by linear interpolation between the modified breakpoints.

After choosing a certain project duration from the time-cost tradeoff curve, a resource leveling is performed on the corresponding solution. Resource capacities are assumed to be fixed in each iteration of this method. Binary search over the different capacities leads to a preferably small maximum capacity. For a fixed resource capacity, the project duration and the given time windows yield topological orderings of the jobs by forward and backward computations of earliest start dates, earliest completion times, latest start dates and latest completion times. Such orderings are suitable to place jobs with respect to the given precedence constraints with a list-scheduling method. If jobs overlap only very little during the list scheduling then with a local search, we try to find candidates for decreasing the processing time by assigning more resources while still satisfying the resource capacities.

Implementation and Tests.

The two-phase approach was tested on instance from T.A. Cook Consultants, Berlin, with 1,000 to 100,000 jobs. The average resource utilization was used as performance criterion. For our instances it was between 95% and 99%. The computation took only a few seconds for the smaller instances and about 10 min for the very large instances. For small instances with around 50 jobs the results of our approach where compared to optimal solutions, computed with a MIP, having a gap of 7-10% in average.

Dealing with Unpredictable Events.

In practice, data is very often not deterministic. Usually, there are assumed to be few (in our data four) possible scenarios with given probabilities for each job. The computation of the expected tardiness of a fixed makespan is already #P-hard for independent random variables of the jobs [2]. As a consequence, in our more complex model we compute only an upper bound on the expected tardiness. We use the upper bound proposed in [4,6] which is shown by them to be computable via the deadline version of the linear time-cost tradeoff problem. Since our instances have series-parallel structure, we also compute a lower bound on the probability that a certain makespan is not exceeded, using the result in [4]. We integrate this information in our time-cost tradeoff curve by providing so called confidence intervals.

Time-Cost Tradeoff-curve and a leveled schedule with a specified resource profile.

Bin Scheduling.

Hoping for helpful structural insights for further improvements of our algorithm, we have investigated what we call the bin scheduling problem. Given fixed resource capacities and identical shifts, i.e. time windows, we aim for scheduling malleable jobs such as to minimize the number of shifts. For the general problem with n jobs, we provide a ϑ(log n)-approximation based on approximation algorithms for the related problem where we do not consider shifts and where we seek to minimize the makespan, which we call the makespan problem.

We could show that as well the makespan problem as also the bin scheduling problem remain NP-hard when the precedence constraints are partial orders with bounded width w≥3. For this case, we provide a FPTAS for the makespan problem, which can also be extended for solving the strip packing problem with precedence constraints of bounded width and bounded strip width. In particular, this yields for both problems first constant approximation algorithms. Using the FPTAS, we also obtain a 3-approximation for the bin scheduling problem.

Back to main page.


Publications.

[P2] Elisabeth Günther, Felix G. König, and Nicole Megow.
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.
In Proceedings of the 7th International Workshop on Approximation and Online Algorithms (WAOA '09), p. 170-181, Lecture Notes in Computer Science, Vol. 5893, 2010.
[P3] Elisabeth Günther, Felix G. König, and Nicole Megow.
The Bin Scheduling Problem.
In Proceedings of 9th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2009), Abbey Rolduc, Netherlands, June 29 - July 3, 2009.
[P7] Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Turnaround Scheduling in Chemical Manufacturing.
In Proceedings of 8th Workshop on Models and Algorithms for Planning and Scheduling (MAPSP 2007), Istanbul, Turkey, July 2-6, 2007. [pdf]
[P8] Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Decision Support and Optimization in Shutdown and Turnaround Scheduling.
INFORMS Journal on Computing 23, pp. 189-204, 2011. (Available as Tech-Report 009-2009)

References.

[1] D.R. Fulkerson.
A network flow computation for project cost curves.
Management Science, 7:167-178, 1961.
[2] J. Hagstrom.
Computational complexity of pert problems.
Networks, 18:139-147, 1988.
[3] J.E. Kelley.
Critical-Path planning and scheduling: Mathematical basis.
Operations Research, 9(3):296-320, 1961.
[4] I. Meilijson and A. Nadas.
Convex majorization with an application to the length of critical paths.
Journal of Applied Probability, 16:671-677, 1979.
[5] S. Phillips and M. I. Dessouky.
Solving the project time/cost tradeoff problem using the minimal cut concept.
Management Science, 24:393-400, 1977.
[6] G. Weiss.
Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and reliability.
Operations Research, 34:595-605, 1986.