Refine
Document Type
- ZIB-Report (3)
- Article (2)
Language
- English (5)
Is part of the Bibliography
- no (5)
Keywords
- Hilbert's projective metric (2)
- lognormal duration (2)
- robust optimization (2)
- activity network (1)
- lognormal distribution (1)
- scheduling (1)
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.
The problem of allocating operating rooms (OR) to surgical cases is a challenging task,
involving both combinatorial aspects and uncertainty handling. In this article,
we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution.
We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end,
we develop an algorithm based on fixed-point iterations to solve the subproblems that
identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based
on real data from a major hospital in Berlin.
Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations
(2016)
The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects
and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution,
and a fixed assignment of jobs to machines must be computed.
We propose a cutting-plane approach to solve the robust counterpart of this optimization problem.
To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities.
The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions.
We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which
only approximation approaches were known. Our model can
be extended to balance the load over several planning periods in a rolling horizon.
We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that:
(i) our approach performs well compared to a previous model that ignored the distribution of case durations;
(ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost;
(iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available.
Finally, we draw a number of managerial implications from these observations.
Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations
(2018)
The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects
and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution,
and a fixed assignment of jobs to machines must be computed.
We propose a cutting-plane approach to solve the robust counterpart of this optimization problem.
To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities.
The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions.
We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which
only approximation approaches were known. Our model can
be extended to balance the load over several planning periods in a rolling horizon.
We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that:
(i) our approach performs well compared to a previous model that ignored the distribution of case durations;
(ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost;
(iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available.
Finally, we draw a number of managerial implications from these observations.