Refine
Year of publication
- 2016 (6) (remove)
Document Type
- ZIB-Report (6) (remove)
Language
- English (6)
Has Fulltext
- yes (6)
Is part of the Bibliography
- no (6)
Keywords
Institute
- Mathematics of Transportation and Logistics (6) (remove)
We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with $k$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are
inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are
located.
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.
A railway operator creates (rolling stock) rotations in order to have a precise master plan for the
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply
traverses a set of operational days while covering trips of the timetable. As it is well known,
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging
and still a topical research subject. Nevertheless, we study a completely different but strongly
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the
rotation itself. Moreover, it turns out that also other European railway operators use exactly the
same methodology (but not terminology). Since a rotation can have many handouts of different
quality, we show how to compute optimal ones through an integer program (IP) by standard
software. In addition, a construction as well as an improvement heuristic are presented. Our
computational results show that the heuristics are a very reliable standalone approach to quickly
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a
computational comparison to the IP approach.
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.
We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.
Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.