Makespan and Tardiness in Activity Networks with Lognormal Activity Durations

Please always quote using this URN: urn:nbn:de:0297-zib-59290
  • We propose an algorithm to approximate the distribution of the completion time (makespan) and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling, where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable. This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits. We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very promising results, especially for the approximation of the mean overtime in operating rooms, for which our algorithm yields results of a similar quality to Monte-Carlo simulations requiring an amount of computing time several orders of magnitude larger.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Guillaume Sagnol, Felix Balzer, Ralf Borndörfer, Claudia Spies, Falk von Dincklage
Document Type:ZIB-Report
Tag:activity network; lognormal distribution; scheduling
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Mxx Computer system organization / 68M20 Performance evaluation; queueing; scheduling [See also 60K25, 90Bxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B36 Scheduling theory, stochastic [See also 68M20]
Date of first Publication:2016/04/26
Series (Serial Number):ZIB-Report (16-23)
ISSN:1438-0064

$Rev: 13581 $