## Report in Wirtschaftsmathematik (WIMA Report)

- 157
- Discrete Parallel Machine Makespan ScheLoc Problem (2015)
- Scheduling-Location (ScheLoc) Problems integrate the separate fields of scheduling and location problems. In ScheLoc Problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling object- ive is minimized. In this paper we consider the Discrete Parallel Machine Makespan (DPMM) ScheLoc Problem where the set of possible machine loc- ations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both NP-hard, so is the corresponding ScheLoc Problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Ex- tensive computational tests show the efficiency of the heuristics.

- 156
- A new solution approach for solving the 2-facility location problem in the plane with block norms (2015)
- Motivated by the time-dependent location problem over T time-periods introduced in Maier and Hamacher (2015) we consider the special case of two time-steps, which was shown to be equivalent to the static 2-facility location problem in the plane. Geometric optimality conditions are stated for the median objective. When using block norms, these conditions are used to derive a polygon grid inducing a subdivision of the plane based on normal cones, yielding a new approach to solve the 2-facility location problem in polynomial time. Combinatorial algorithms for the 2-facility location problem based on geometric properties are deduced and their complexities are analyzed. These methods differ from others as they are completely working on geometric objects to derive the optimal solution set.

- 155
- A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane (2014)
- A single facility problem in the plane is considered, where an optimal location has to be identified for each of finitely many time-steps with respect to time-dependent weights and demand points. It is shown that the median objective can be reduced to a special case of the static multifacility median problem such that results from the latter can be used to tackle the dynamic location problem. When using block norms as distance measure between facilities, a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation between dynamic location problems for T time periods and T-facility problems, this algorithm can also be applied to the static 2-facility location problem.

- 153
- Transit Dependent Evacuation Planning for Kathmandu Valley: A Case Study (2014)
- Due to the increasing number of natural or man-made disasters, the application of operations research methods in evacuation planning has seen a rising interest in the research community. From the beginning, evacuation planning has been highly focused on car-based evacuation. Recently, also the evacuation of transit depended evacuees with the help of buses has been considered. In this case study, we apply two such models and solution algorithms to evacuate a core part of the metropolitan capital city Kathmandu of Nepal as a hypothetical endangered region, where a large part of population is transit dependent. We discuss the computational results for evacuation time under a broad range of possible scenarios, and derive planning suggestions for practitioners.

- 152
- A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions (2014)
- A new algorithm for optimization problems with three objective functions is presented which computes a representation for the set of nondominated points. This representation is guaranteed to have a desired coverage error and a bound on the number of iterations needed by the algorithm to meet this coverage error is derived. Since the representation does not necessarily contain nondominated points only, ideas to calculate bounds for the representation error are given. Moreover, the incorporation of domination during the algorithm and other quality measures are discussed.

- 151
- Optimization Models to Enhance Resilience in Evacuation Planning (2014)
- We argue that the concepts of resilience in engineering science and robustness in mathematical optimization are strongly related. Using evacuation planning as an example application, we demonstrate optimization techniques to improve solution resilience. These include a direct modelling of the uncertainty for stochastic or robust optimization, as well as taking multiple objective functions into account.

- 150
- Hierarchical Edge Colorings and Rehabilitation Therapy Planning in Germany (2014)
- In this paper we give an overview on the system of rehabilitation clinics in Germany in general and the literature on patient scheduling applied to rehabilitation facilities in particular. We apply a class-teacher model developed to this environment and then generalize it to meet some of the specific constraints of inpatient rehabilitation clinics. To this end we introduce a restricted edge coloring on undirected bipartite graphs which is called group-wise balanced. The problem considered is called patient-therapist-timetable problem with group-wise balanced constraints (PTTPgb). In order to specify weekly schedules further such that they produce a reasonable allocation to morning/afternoon (second level decision) and to the single periods (third level decision) we introduce (hierarchical PTTPgb). For the corresponding model, the hierarchical edge coloring problem, we present some first feasibility results.

- 149
- Edgeworth expansions for lattice triangular arrays (2014)
- Edgeworth expansions have been introduced as a generalization of the central limit theorem and allow to investigate the convergence properties of sums of i.i.d. random variables. We consider triangular arrays of lattice random vectors and obtain a valid Edgeworth expansion for this case. The presented results can be used, for example, to study the convergence behavior of lattice models.

- 148
- Monitoring time series based on estimating functions (2014)
- A large class of estimators including maximum likelihood, least squares and M-estimators are based on estimating functions. In sequential change point detection related monitoring functions can be used to monitor new incoming observations based on an initial estimator, which is computationally efficient because possible numeric optimization is restricted to the initial estimation. In this work, we give general regularity conditions under which we derive the asymptotic null behavior of the corresponding tests in addition to their behavior under alternatives, where conditions become particularly simple for sufficiently smooth estimating and monitoring functions. These regularity conditions unify and even extend a large amount of existing procedures in the literature, while they also allow us to derive monitoring schemes in time series that have not yet been considered in the literature including non-linear autoregressive time series and certain count time series such as binary or Poisson autoregressive models. We do not assume that the estimating and monitoring function are equal or even of the same dimension, allowing for example to combine a non-robust but more precise initial estimator with a robust monitoring scheme. Some simulations and data examples illustrate the usefulness of the described procedures.

- 147
- On the Generality of the Greedy Algorithm for Solving Matroid Base Problems (2013)
- It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions.