Skip to main content
main-content

Über dieses Buch

This volume contains a selection of 128 papers presented in lectures during the international scientific symposium "Operations Research 2005" (OR 2005) held at the University of Bremen, September 7-9, 2005. This international conference took place under the auspices of the German Operations Research Society (GOR).

The symposium had about 600 participants from countries all over the world. It attracted academics and practitioners working in various fields of Operations Research and provided them with the most recent advances in Operations Research as well as related areas in Economics, Mathematics, and Computer Science including the special interest streams Logistics and New Maritime Businesses.

The program consisted of 3 plenary and 15 semi-plenary talks and about 400 contributed presentations selected by the program committee to be presented in 20 sections.

Inhaltsverzeichnis

Frontmatter

Dissertation Award of the GOR

Frontmatter

Zeitkontinuität in zeitdiskreten Modellen — Neue Ansätze für die Produktionsplanung in der Prozessindustrie

Christopher Sürie

A Hierarchical Production Planning Approach for Multiprocessor Flow Shops

We consider the lot-sizing and scheduling problem for multiprocessor flow shops. In this environment, lot-sizing and scheduling are interdependent. A hierarchical planning approach is presented together with an overview of the developed solution procedures. The objective is to minimizes setup, inventory holding and back-order costs as well as the mean flow time. Computational results are illustrated.

Daniel Quadt

Representing Labor Demands in Airport Ground Staff Scheduling

Airport ground staff scheduling gives rise to a number of challenging optimization problems. We give an overview of airport shift scheduling, focusing on suitable representations for labor demands. We argue that especially in short-term shift planning, traditional models using a demand curve representation of workloads are not always appropriate in ground handling. We therefore formulate task-level shift planning as the problem of creating a cost-minimal set of shift duties which cover the given set of work tasks. The resulting model integrates aspects from shift scheduling and vehicle routing. Depending on the number of additional constraints imposed, different solution techniques seem appropriate. We outline a branch-andprice algorithm which is able to solve an important class of task-level shift planning problems from the practice of airlines and ground handling companies to proven optimality within reasonable run-times.

Jörg Herbers

Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a Few Seconds

Thorsten Koch

Diploma Award of the GOR

Frontmatter

Standortplanung von Einsatzkräften bei Großereignissen

Großveranstaltungen sind auf Grund der enormen Menschenansammlungen eng mit einem erhöhten Gefahrenpotenzial verbunden. Zur Absicherung müssen deswegen immer Einsatzkräfte von Rettungsdiensten, Polizei, Feuerwehr etc. vor Ort sein. Für die verantwortlichen Entscheidungsträger ist es jedoch ein schwieriges Problem, die Anzahl sowie die Standorte der benötigten Einsatztrupps festzulegen. Mittels einer Analyse der praktischen Einsatzplanung werden konkrete Fragestellungen definiert, die die Basis für eine Modellierung bilden. An Hand verschiedener mathematischer Modelle und deren Lösung wird deutlich, dass Instrumente des Operations Research die Entscheidungsfindung der Verantwortlichen unterstützen können. Die vorgestellten Modelle konnten auf einen praktischen Fall einer Großveranstaltung in Dresden mit 50.000 Besuchern erfolgreich angewendet werden.

Julia Drechsel

Logistics

Frontmatter

Customer Selection and Profit Maximization in Vehicle Routing Problems

Deniz Aksen, Necati Aras

A Decision Support System for Strategic and Operational Planning of Road Feeder Services

Paul Bartodziej, Ulrich Derigs, Boris Grein

Mehrdepot-Umlaufplanung: Berücksichtigung von Verschiebeintervallen für Fahrten in einem Time-Space-Netzwerk-basierten Modell

Stefan Bunte, Natalia Kliewer, Leena Suhl

Adaptive Dienst- und Umlaufplanung im ÖPNV

Die Probleme der Umlauf- und Dienstplanung im Öffentlichen Personennahverkehr (ÖPNV) werden traditionell nacheinander gelöst. Somit liegen für die Generierung möglicher Dienste feste Umläufe zugrunde. Das führt oft dazu, dass die Dienstpläne unzulässig bzw. nicht kostenoptimal sind. Wir präsentieren ein adaptives Verfahren, dass der Dienstplanung eine Rückkopplung zu der Umlaufplanung erlaubt. Dabei können bei der Dienstplanung die gegebenen Umläufe ggf. in gewissem Maße verändert werden, so dass ihre Gesamtkosten aber optimal bleiben. Die durchgeführten Tests zeigen, dass durch diese Rückkopplung eine enorme Verbesserung der Dienstpläne erreicht werden kann.

Vitali Gintner, Stefan Kramkowski, Ingmar Steinzen, Leena Suhl

Timber Transport Vehicle Routing Problems: Formulation and Heuristic Solution

We present a model formulation and a Tabu Search based solution method for the Timber Transport Vehicle Routing Problem (TTVRP). A fleet of

m

trucks which are situated at the respective homes of the truck drivers has to fulfil

n

transports of round timber between different wood storage locations and industrial sites. All transports are carried out as full truck loads. Since the full truck movements are predetermined our objective is to minimize the overall distance of empty truck movements. In addition to the standard VRP we have to consider weight constraints at the network, multi-depots, and time windows. The optimum solution of this problem with common solver software is only possible for very small instances. Therefore we develop a customized heuristic to solve real-life problems. We modify the traditional Tabu Search by delimiting the neighborhood in some iterations and verify our heuristic with extensive numerical studies.

Manfred Gronalt, Patrick Hirsch

Robustness in the Context of Autonomous Cooperating Logistic Processes: A Sustainability Perspective

Autonomous cooperating logistic processes seem to be a promising approach to increase the robustness of logistics systems. Searching for the necessary organizational prerequisites for the successful implementation and sustainment of autonomous cooperating logistic processes we pick up the concept of robustness and use the New Systems Theory to outline a notion of organizational robustness, which can be regarded as an important factor enabling businesses to adopt innovations in spite of related uncertainties.

Lars Arndt, Georg Müller-Christ

Open Vehicle Routing Problem with Time Deadlines: Solution Methods and an Application

In the open route version of the well-known vehicle routing problem, vehicles are not required to return to the depot; or if they are required, then they return by traveling the same route back. In this study, we present a modified Clarke-Wright parallel savings algorithm, a nearest insertion algorithm and a tabu search heuristic for the open vehicle routing problem with time deadlines. Some random test problems and a real-life school bus routing problem are solved by these heuristics, and results are compared.

Zeynep Özyurt, Deniz Aksen, Necati Aras

An Optimal Control Policy for Crossdocking Terminals

Crossdocking terminals are transhipment facilities without stock, for the rapid consolidation and shipment of products. The difference to traditional distribution centers is the complete elimination of all storage functions. In consequence of this elimination the incoming and outgoing shipments have to be exactly coordinated to achieve a transshipment operation at minimum cost. This paper describes a mixed-integer model for a centralized optimal control policy for crossdocking facilities, which takes into account the shipments of goods to the crossdocking terminal, the transfers inside the terminal as well as the shipments to the customers. A Branch-and-Bound algorithm has been applied to obtain an exact solution for the optimization model which is tested on different data sets. The results show that an exact solution can be obtained for small instances. Finally, the results for a decomposed model are presented. The decomposition yields faster results for larger instances and therefore is more applicable in practice.

Matthias Stickel, Kai Furmans

An Enumerative Approach to Rail-Truck Intermodal Transportation of Mixed Shipments

Manish Verma, Vedat Verter

Some Remarks on the Stability of Production Networks

The increasing complexity of production and logistics networks and the requirement of higher flexibility lead to a change of paradigm in control: Autonomously controlled systems where decisions are taken by parts or goods themselves become more attractive. The question of stability is an important issue for the dynamics of such systems. In this paper we are going to touch this question for a special production network with autonomous control. The stability region for a corresponding fluid model is found empirically. We point out that further mathematical investigations have to be undertaken to develop some stability criteria for autonomous systems.

Bernd Scholz-Reiter, Fabian Wirth, Michael Freitag, Sergey Dashkovskiy, Thomas Jagalski, Christoph de Beer, Björn Rüffer

Simulating Dispatching Strategies for Automated Container Terminals

Dirk Briskorn, Sönke Hartmann

New Maritime Businesses

Frontmatter

Integration of Berth Allocation and Crane Assignment to Improve the Resource Utilization at a Seaport Container Terminal

This talk deals with the combination of two decision problems, which occur consecutively while planning the charge and discharge operations of container ships in container terminals. The Berth Allocation Problem (BAP) considers the allocation of ships to berths in the course of time. The Crane Assignment Problem (CAP) addresses the assignment of quay cranes to ships. We provide a heuristic approach for the integrated solution of these problems and present computational results based on real world data.

Frank Meisel, Christian Bierwirth

Simulation der Supply Chain für Offshore-Wind-Energie-Anlagen

Sebastian Gabriel, Carsten Boll

Modeling and Solution for Yard Truck Dispatch Planning at Container Terminal

This research addresses the dispatch planning of yard trucks to support transferring tasks of containers between shipside and yard areas. With considering the fundamental operations of fixed number of trucks serving one quay crane, we discuss the possible serving status of yard trucks in the connection of task by task. Upon these limited connection patterns, we formulate a min-max nonlinear integer programming model for dispatching yard trucks to efficiently complete the system works. A heuristic approach with two phases of selecting locations for stored or picked containers then assigning served trucks is suggested. We apply it with four proposed principles of location assignment on the analysis of the real-world cases from a dedicated terminal. The results show that the closest position assignment principle is better in the larger scale problems. However, more trucks than the critical number can not increase the performance.

Hua-An Lu, Jing-Yi Jeng

Strategic Tools for the Sustainable Development of Maritime Regions

In line with the sustainable development of maritime regions and the design of new maritime businesses strategic management tools can be applied. These tools take into account regional characteristics as well as new value added processes within supply chains. Moreover they are based on the concept of knowledge regions. A knowledge region means a better communication and knowledge management between enterprises and decision makers in a region. Knowledge management is used to improve the personal, business process orientated and informational interfaces between decision makers. In this paper these tools are presented; their application within regional decision processes will be demonstrated.

Hans-Dietrich Haasis, Oliver Möllenstädt

Production & Supply Chain Management

A Two-echelon Model for Inventory and Returns

We consider an Markovian model for a two-echelon inventory/return system. The system consists of a supply plant with infinite capacity and a central warehouse for inventory and returns. There is also a number of local warehouses which are also able to re-manufacture products. To obtain a high service level of handling inventory and returns, lateral transshipment of demands is allowed among the local warehouses.

Allen H. Tai, Wai-Ki Ching

Bestimmung von Losgrößen, Transportzyklen und Sicherheitsbeständen in unternehmensübergreifenden Wertschöpfungsketten

In dem Beitrag wird ein zweistufiges Planungskonzept vorgestellt, um im Zuge der Gestaltung einer Supply Chain die Losauflagen, Transportzyklen und Sicherheitsbestände für die Produkte der Supply Chain festzulegen. In der ersten Planungsstufe werden die Transport- und Losgrößen festgelegt. Die zweite Stufe bestimmt unter Einhaltung eines vorgegebenen Serviceniveaus am Ende der Supply Chain die notwendigen Sicherheitsbestände je Lagerstufe.

Heinrich Kuhn, Fabian J. Sting

A Group Setup Strategy for PCB Assembly on a Single Automated Placement Machine

In this paper, a novel approach for group setup strategies has been presented fot the case of a single collect-and-place assembly machine. Minimizing the makespan for a given number of batches of different PCB types is regarded as the objective function. The proposed methodology applies machine-specific algorithms for optimizing magazine setups for each PCB family and generating placement sequences for each PCB type. Thus, realistic assembly times and optimized magazine setups are used in contrast to other conventional approaches for grouping PCBs. Additionally, batch sizes are also integrated into the group formation procedure. Development of other group formation methodologies based on realistic assembly times is considered as a future research topic.

Ihsan Onur Yilmaz, Hans-Otto Günther

Optionsbündelung und Fertigungsablauf in der Automobilindustrie

Bei der Optionsbündelung werden einzelne Ausstattungsmerkmale (Optionen) zu Paketen (Bündeln) zusammengefasst. Im Mittelpunkt dieses Beitrags steht die Beantwortung der Frage, ob eine solche Optionsbündelung den Produktionsablauf positiv beeinflusst. Dabei richtet sich das Hauptaugenmerk auf eine Variantenfließfertigung, die etwa in der Endmontage der Automobilindustrie eine dominierende Stellung einnimmt. Eine umfangreiche Simulationsstudie soll den positiven Effekt der Optionsbündelung nachweisen. Ferner wird untersucht, welche Bündelungsart im Rahmen einer Variantenfließfertigung besonders viel versprechend erscheint.

Nils Boysen, Christian M. Ringle

A Heuristic Method for Large-Scale Batch Scheduling in the Process Industries

In the process industries, final products arise from chemical and physical transformations of materials on processing units. In batch production mode, the total requirements for intermediate and final products are divided into individual batches. Storage facilities of limited capacity are available for stocking raw materials, intermediates, and final products. We present a novel approach to solving large-scale instances of the minimum-makespan production scheduling problem. The basic idea consists in constructing a production schedule by concatenating copies of a cyclic subschedule. For generating an appropriate subschedule we formulate a mixed-integer nonlinear program providing the set of batches of one cycle and the number of cycles needed to satisfy the primary requirements. The subschedule is then obtained by allocating the processing units, intermediates, and storage facilities over time to the batches executed in the cycle.

Norbert Trautmann, Christoph Schwindt

Planning Disassembly for Remanufacturing Under a Rolling Schedule Environment

This contribution examines the performance of both exact as well as heuristic solution methods for the disassemble-to-order problem under a rolling schedule planning environment. The results indicate that the problems-pecific heuristic exhibits good average performance, and low dispersion and low maximum penalty values. Even so, the cost penalties remain higher than that of applying exact methods to the rolling schedule problem.

Tobias Schulz, Ian M. Langella

An LP-based Heuristic Approach for Strategic Supply Chain Design

A novel heuristic approach is proposed for solving a large scale facility location problem arising in supply chain design. The problem formulation includes many practical aspects such as a dynamic planning horizon, generic supply chain structure, inventory and distribution of goods, budget constraints, and storage limitations. Moreover, facility location decisions are modelled through the gradual relocation of existing facilities to new sites over a given planning horizon. The heuristic approach explores the solution of the linear relaxation of the problem. It successively rounds the fractional variables corresponding to the 0/1 decisions of changing the facilities’ status (i.e., open new / close existing facilities), and it is also used to roughly estimate the total number of facility configuration changes over the planning horizon. The proposed heuristic performs very well on a large set of randomly generated problems, producing feasible solutions that on average only deviate 1.4% from the optimum.

Rafael Velásquez, M. Teresa Melo, Stefan Nickel

Der Einfluss von alternativen Bezugsquellen auf die optimale Beschaffungsstrategie

In dieser Arbeit wird mithilfe eines Newsboy-Ansatzes der Einfluss von (kurzfristigen) Spotmärkten auf langfristige Kontrakte zwischen Supply Chain Partnern betrachtet.

Ivo Neidlein

Distributed Planning in Product Recovery Networks

We consider a scenario, where a network of disassembly companies treats waste electronic equipment due to environmental regulation. Legal requirements like collection and recycling targets are formulated as network wide constraints of a network flow model. With regard to a distributed decision situation where a focal company with bounded knowledge coordinates activities of the disassembly network, fulfilment of these common constraints requires coordination. Assuming that the focal company’s aim is to maximise network wide profit, a decentralised problem formulation using Lagrangean relaxation is presented.

Eberhard Schmid, Grit Walther, Thomas Spengler

Valuing Product Portfolios Under Uncertainty and Limited Capacity

This paper deals with the investigation of product portfolios in a make-to-order manufacturing setting characterized by demand uncertainty and limited production capacity. Using a simple two-period model we address the general question of planning under uncertainty and show the profit/cost implications of an individual contract in the portfolio and their dependence on capacity tightness.

Philippe Schiltknecht, Marc Reimann

Entwicklung eines reaktiven Schedulingsystems für die Prozessindustrie

In dem vorliegenden Beitrag wurde ein reaktives Schedulingsystem vorgestellt, das den Entscheidungsprozess bei Umplanungsaktivitäten unterstützen soll. Als Störungsursachen wurden Anlagenausfälle berücksichtigt. Anhand eines numerischen Beispiels wurde die Funktionsweise des Systems erläutert. Als Erweiterungen für das System sind die Berücksichtung zusätzlicher Störereignisse und die Implementierung alternativer Schedulingmethoden vorgesehen.

Ulf Neuhaus, Hans Otto Günther

Recovery Knowledge Acquisition in Medium and Long Term Planning of a Joint Manufacturing / Remanufacturing System

In this work, the impact of knowledge acquisition in product recovery on optimal stock-keeping decisions as well as on the question on whether at all and when to start remanufacturing is discussed.

Rainer Kleber

Finance, Banking and Insurance

Frontmatter

Performance Measurement of Hedge Fund Indices - Does the Measure Matter?

It does not matter too much which performance measure one chooses to evaluate hedge funds. Because the newer performance measurement approaches result in rankings that are the same and thus result in the same assessments of hedge funds, use of the classic Sharpe ratio (even if it displays some undesirable features) is justified, at least from a practical perspective.

The results of this study will be helpful for investing in hedge funds that are constructed like indices. However, an important question is whether the choice of a specific performance measure matters when evaluating single hedge funds. The findings of the current study have motivated us to procure return data for single hedge funds in order to analyse this question in the future. However, the indices we examined in this paper appear to be representative for single hedge funds insofar as the return distributions deviate significantly from a normal distribution.

Another question not answered in this study is the relevance of performance measures that are evolved on the basis of correlations, such as the Jensen, Treynor and Treynor-Black measures. This question should also be examined in future studies.

Martin Eling, Frank Schuhmacher

On the Applicability of a Fourier Based Approach to Integrated Market and Credit Portfolio Models

Based on a version of the well-known credit portfolio model CreditMetrics extended by correlated interest rate and credit spread risk the application of a Fourier based method for calculating credit risk measures is demonstrated. The accuracy and speed of this method is compared with standard Monte Carlo simulation by means of numerical experiments.

Peter Grundke

Dynamic Replication of Non-Maturing Assets and Liabilities

Michael Schürle

Portfolio Optimization Under Partial Information and Convex Constraints in a Hidden Markov Model

In a continuous-time hidden Markov model (HMM) for stock returns we consider an investor who wishes to maximize the expected utility of terminal wealth. As a means to deal with the resulting highly risky strategies we impose convex constraints on the trading strategies covering e.g. short selling restrictions. Based on HMM filtering methods we show how to reformulate this model with partial information as a model with full information. Then results on portfolio optimization under constraints are used to give a verification result. By its application an optimal trading strategy can be computed. Numerical results are provided.

Jörn Sass

Robuste Portfoliooptimierung: Eine kritische Bestandsaufnahme und ein Vergleich alternativer Verfahren

Ulf Brinkmann

Effizienzanalyse deutscher Banken mit Data Envelopment Analysis und Stabilitätsanalysen

In dieser Arbeit wurde auf die Problematik der Stabilität der Ergebnisse einer DEA-Effizienzmessung eingegangen. Der besondere Beitrag der Arbeit liegt in der Vorstellung eines DEA-Modells zur Stabilitätsanalyse, mit dem simultan die Änderungen aller Daten für jede EE betrachtet werden kann. Daneben kann dieses Modell in der betrieblichen Praxis zur Simulation verschiedener Szenarien und deren Auswirkung auf die Effizienz benutzt werden. Die Anwendung des Modells wurde in einer Fallstudie demonstriert.

Armin Varmaz

Artificial Intelligence and Fuzzy Logic

Frontmatter

Duality in Fuzzy Multiple Objective Linear Programming

A class of fuzzy multiple objective linear programming (FMOLP) problems with fuzzy coefficients based on fuzzy relations is introduced, the concepts of feasible and (alpha,beta)-maximal and minimal solutions are defined. The class of crisp (classical) MOLP problems can be embedded into the class of FMOLP ones. Moreover, for FMOLP problems a new concept of duality is introduced and the weak and strong duality theorems are derived.

Jaroslav Ramík

Variable Subset Selection for Credit Scoring with Support Vector Machines

Support Vector Machines (SVM) are very successful kernel based classification methods with a broad range of applications including credit scoring and rating. SVM can use data sets with many variables even when the number of cases is small. However, we are often constrained to reduce the input space owing to changing data availability, cost and speed of computation. We first evaluate variable subsets in the context of credit scoring. Then we apply previous results of using SVM with different kernel functions to a specific subset of credit client variables. Finally, rating of the credit data pool is presented.

Ralf Stecking, Klaus B. Schebesch

Genetically Constructed Kernels for Support Vector Machines

Data mining for customer relationship management involves the task of binary classification, e.g. to distinguish between customers who are likely to respond to direct mail and those who are not. The support vector machine (SVM) is a powerful learning technique for this kind of problem. To obtain good classification results the selection of an appropriate kernel function is crucial for SVM. Recently, the evolutionary construction of kernels by means of meta-heuristics has been proposed to automate model selection. In this paper we consider genetic algorithms (GA) to generate SVM kernels in a data driven manner and investigate the potential of such hybrid algorithms with regard to classification accuracy, generalisation ability of the resulting classifier and computational efficiency. We contribute to the literature by: (1) extending current approaches for evolutionary constructed kernels; (2) investigating their adequacy in a real world business scenario; (3) considering runtime issues together with measures of classification effectiveness in a mutual framework.

Stefan Lessmann, Robert Stahlbock, Sven Crone

Optimierung von Warteschlangensystemen durch Approximation mit Neuronalen Netzen

Frank Köller, Michael H. Breitner

Aktienkursprognose anhand von Jahresabschlussdaten mittels Künstlicher Neuronaler Netze und ökonometrischer Verfahren

Thorsten Poddig, Oxana Enns

Discrete and Combinatorial Optimization

Frontmatter

On the Computational Performance of a Semidefinite Programming Approach to Single Row Layout Problems

Miguel F. Anjos, Anthony Vannelli

On Some Probability Inequalities for Some Discrete Optimization Problems

Probabilistic analysis of algorithms for discrete optimization problems is the subject of many recent investigations (Karp, Frieze, Radhavan at al). Probability inequalities of well known researchers (Chernov, Hoefding at al) are widely exploited in this works. The paper aims at demonstrating some results of probabilistic analysis of algorithms for a number of well known combinatorial problems that use another efficient (productive) probability inequalities (of Bernstein, Borovkov, Petrov, etc.). The results deal with proofs of asymptotical optimality of polynomial approximation algorithms for solving the traveling salesman problem, the bin packing problem, the multi-index assignment problem, the uncapacitated facility location problem, the problem of finding the regular connected subgraph of maximum weight

Edward Kh. Gimadi

Two-Dimensional Cutting Stock Problem Under Low Demand: a Study Case

This work revised a heuristic to determine an integer solution to one-dimensional cutting stock problems and extend it to two-dimensional problems. Real-world instances from a Brazilian metallic frameworks industry were solved. The proposed heuristic was able to improve several instances’ solution. For future research we intend to analyze more instances from the industry and also test some modifications on the heuristic proposed which were successful when applied to solve one-dimensional problems. Also, we intend to compare the proposed approach with the one by Riehme et al. 1996.

Kelly Cristina Poldi, Marcos Nereu Arenales, Andrea Carla G. Vianna

Length-Bounded and Dynamic k-Splittable Flows

Classical network flow problems do not impose restrictions on the choice of paths on which flow is sent. Only the arc capacities of the network have to be obeyed. This scenario is not always realistic. In fact, there are many problems for which, e.g., the number of paths being used to route a commodity or the length of such paths has to be small. These restrictions are considered in the length-bounded

k

-splittable

s

-

t

-flowproblem: The problem is a variant of the well known classical

s

-

t

-flow problem with the additional requirement that the number of paths that may be used to route the flow and the maximum length of those paths are bounded. Our main result is that we can efficiently compute a length-bounded

s

-

t

-flow which sends one fourth of the maximum flow value while exceeding the length bound by a factor of at most 2. We also show that this result leads to approximation algorithms for dynamic

k

-splittable

s

-

t

-flows.

Maren Martens, Martin Skutella

Locating and Sizing Bank-Branches by Opening, Closing or Maintaining Facilities

The bank-branch restructuring problem seeks to locate bank-branches by maintaining, closing, or opening branches, to provide the service required by clients, at minimum total cost. This nonlinear problem, due to the existence of economies of scale, is formulated as a mixed binary, integer linear model. The model obtained can be solved by a ready-available software. However, due to the problem combinatorial nature, only small size instances can be solved. Thus, we also propose a local search heuristic that iteratively improves the solution obtained for a related linear problem by applying drop and swap operations. The computational experiments performed show the effectiveness and efficiency of the proposed heuristic.

Marta S. Rodrigues Monteiro, Dalila B. M. M. Fontes

Simulated Annealing Based Algorithm for the 2D Bin Packing Problem with Impurities

B. Beisiegel, J. Kallrath, Y. Kochetov, A. Rudnev

LP-based Genetic Algorithm for the Minimum Graph Bisection Problem

We investigate the minimum graph bisection problem concerning partitioning the nodes of a graph into two subsets such that the total weight of each set is within some lower and upper limits. The objective is to minimize the total cost of edges between both subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and in parallel computing. We present an integer linear programming formulation for this problem. We develop a primal heuristic based on a genetic algorithm, incorporate it in a branch-and-cut framework and present some computational results.

Michael Armbruster, Marzena Fügenschuh, Christoph Helmberg, Nikolay Jetchev, Alexander Martin

Scheduling Departures at Airports — a MILP Approach

Florian Büchting, Petra Huhn

Optimization of Sheet Metal Products

Linear flow splitting enables the forming of branched sheet metal products in integral style. To optimize those products design parameters have to be based on market requirements. We show that methods that are also used in Operations Research can, in principle, be applied to solve these optimization problems. For this, engineers provide constructive parameters that describe the demands of customers in a mathematical way. Based on these descriptions, we develop a two-stage model. First, a topology and shape optimization of branched sheet metal products is carried out, where the best-possible product is automatically designed by solving some OR models. Then, in stage two, we deal with the problem of how to incorporate manufacturing constraints for sheet metal products. The solution to this model corresponds to a construction plan. The entire approach is demonstrated in the design and construction of a cable conduit.

Herbert Birkhofer, Armin Fügenschuh, Ute Günther, Daniel Junglas, Alexander Martin, Thorsten Sauer, Stefan Ulbrich, Martin Wäldele, Stephan Walter

Modellierung von Entscheidungsproblemen in der Lehre - Ein Erfahrungsbericht

Karel Vejsada

A Column Generation Approach to Airline Crew Scheduling

The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel “rapid branching” IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.

Ralf Borndörfer, Uwe Schelten, Thomas Schlechte, Steffen Weider

A Flexible Model and Efficient Solution Strategies for Discrete Location Problems

We propose a new formulation for the Discrete Ordered Median Problem (DOMP) which has first been introduced in [5]. For this new formulation we present several variable fixing strategies and one family of valid inequalities which are used in a specialized branch & cut procedure. Extensive computational results show that using this method, problems can be solved, which are more than twice as large as those that can be solved by existing solution approaches.

Alfredo Marín, Stefan Nickel, Justo Puerto, Sebastian Velten

Finding Feasible Solutions to Hard Mixed-integer Programming Problems Using Hybrid Heuristics

In current mixed-integer programming (MIP) solvers heuristics are used to find feasible solutions before the branch-and-bound or branchand-cut algorithm is applied to the problem. Knowing a feasible solution can improve the solutions found or the time to solve the problem very much. This paper discusses hybrid heuristics for this purpose. Hybrid in this context means that these heuristics use the branch-and-bound algorithm to search a smaller subproblem. Several possible hybrid heuristics are presented and computational results are given.

Philipp M. Christophel, Leena Suhl, Uwe H. Suhl

Optimisation of the Variant Combination of Control Units Considering the Order History

In modern cars, an increasing number of functions are integrated in single control units. Some of the functions can be ordered as optional equipment by the customer. To reduce costs, variants of the control units are created differing in hardware and software. Variants are created by not populating sections of a circuit board. Each additional variant of a control unit causes expenses for logistics and development. Today the process for the determination of the variants is not automated. Non-technical dependencies like equipment packages or common ordered equipment combinations can only partially be taken into account. In this article we formulate this problem and show how existing information on the manufacturer’s side can serve as a base for an optimisation of the variants. We also show how the problem can be transformed into a warehouse location problem, so that it can be solved in short time. Finally, the results of an application example are presented.

Bernd Hardung, Thomas Kollert

Solving a Dynamic Real-Life Vehicle Routing Problem

Real-life vehicle routing problems encounter a number of complexities that are not considered by the classical models found in the vehicle routing literature. In this paper we consider a dynamic real-life vehicle routing problem which is a combined load acceptance and generalised vehicle routing problem incorporating a diversity of practical complexities. Among those are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, route restrictions associated to orders and vehicles, and drivers’ working hours. We propose iterative improvement approaches based on Large Neighborhood Search. Our algorithms are characterised by very fast response times and thus, can be used within dynamic routing systems where input data can change at any time.

Asvin Goel, Volker Gruhn

Heuristic Enhancements to the k-best Method for Solving Biobjective Combinatorial Optimisation Problems

Sarah Steiner, Tomasz Radzik

Routing and Networks

Frontmatter

Sollen Anschlussverbindungen bei Verspätungen unterbrochen werden? — Ein Ansatz zur Formulierung der Fragestellung in der Theorie des Option Pricing

Ina Bauerdorf

Some Remarks on the GIST Approach for the Vehicle Routing Problem with Pickup and Delivery and Time Windows (VRPPDTW)

Ulrich Derigs, Thomas Döhmer

Analyse der Beschleunigung des A*-Verfahrens durch verbesserte Schätzer für die Restdistanz

Felix Hahne

Modelling Transport Networks by Means of Autonomous Units

The concept of autonomous units to model distributed logistic processes and their interactions in a transport network is introduced. Autonomous units provide a general approach with rigorous semantics that allow the visual modelling of logistic processes in the transport domain in a systematic and structured way. Differing from existing models it especially incorporates the specification of autonomous or self-controlled behaviour of the participating actors. It means that the respective actions are not always predefined but allow for autonomous choice. By example in this paper a negotiation based approach is introduced. Due to this approach being formal and well-defined it supports testing and verification of required properties of the modelled systems at the level of specification.

Karsten Hölscher, Peter Knirsch, Hans-Jörg Kreowski

Routing in Line Planning for Public Transport

The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a given demand can be satisfied. There are two objectives. Passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commodity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path routings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.

Marc E. Pfetsch, Ralf Borndörfer

Tourenplanung mittelständischer Speditionsunternehmen in Stückgutkooperationen

Um gestiegenen Kundenansprüchen gerecht zu werden, arbeiten mittelständische Speditionsunternehmen zunehmend in Stückgutkooperationen zusammen. Für die einzelnen Kooperationspartner ergeben sich dabei eine Reihe neuer Anforderungen bei der Erstellung eines Tourenplans. Neben der Berücksichtigung heterogener Fahrzeuge und Kundenzeitfenster sowie simultaner Auslieferung und Einsammlung sind z.B. ein mehrfacher Fahrzeugeinsatz vorzusehen und Belegungszeiten der Rampen im Depot zu berücksichtigen. Das betrachtete Tourenplanungsproblem wird als gemischt-ganzzahliges lineares Programm formuliert. Da eine Lösung mit Cplex 9.0 nur für kleine Instanzen in akzeptabler Zeit möglich ist, werden heuristische Lösungsverfahren und erste Performance-Ergebnisse vorgestellt.

Julia Rieck, Jürgen Zimmermann

Closed Networks of Generalized S-queues with Unreliable Servers

Kersten Tippner

OR Applications in Health and Life Sciences

Frontmatter

A Set Packing Approach for Scheduling Elective Surgical Procedures

The efficient scheduling of surgical procedures to operating rooms in a hospital is a complex problem due to limited resources (e.g. medical staff, equipment) and conflicting objectives (e.g. reduce running costs and increase staff and patient satisfaction). A novel approach for scheduling elective surgeries over a short-term horizon is proposed which takes explicit consideration of these aspects. The problem is formulated as a set packing problem and solved optimally through column generation and constraint branching. Good results were obtained for instances from the literature.

R. Velásquez, M. T. Melo

Locating Health Facilities in Nouna District, Burkina Faso

The Nouna health district in Burkina Faso, Africa, has a population of approximately 275,000 people living in 290 villages, who are served by 23 health facilities. At present, the time and effort required in travelling to a health facility (especially during the rainy season) is, for many people, a deterrent to seeking proper medical care. As one step toward improving health care for the people in the district, this study focuses on the problem of optimally locating new health facilities. In light of a government goal that every village should have a health facility within 10 kilometers, the basic model we use for this problem is a covering model, which we then further adapt to the specific situation in Nouna. In this paper we will discuss our application of location analysis techniques to this problem, including an analysis of the current situation, the creation of an appropriate model, solution techniques, and final results.

Cara Cocking, Steffen Flessa, Gerhard Reinelt

A Dual Algorithm to Obtain Highly Practical Solutions in Static Multileaf Collimation

Philipp Süss

Challenges in the Optimization of Biosystems II: Mathematical Modeling and Stability Analysis of Gene-Expression Patterns in an Extended Space and with Runge-Kutta Discretization

Mesut Taştan, Stefan W. Pickl, Gerhard Wilhelm Weber

Continuous Optimization

Frontmatter

Wavelet Schemes for Linear-Quadratic Elliptic Control Problems

This paper discusses the efficient numerical solution of a class of continuous optimization problems which are characterized by minimizing a tracking-type quadratic control functional subject to constraints in form of a linear elliptic partial differential equation (PDE) together with appropriate boundary conditions. For such problems, discretizations in terms of (domain-adapted biorthogonal spline-)wavelets offer several favorable properties over conventional approaches: from the evaluation of non-integer Sobolev norms in the objective functional over well-conditioned coupled linear systems of equations up to adaptive solution schemes with provable convergence and optimal convergence rates.

Angela Kunoth

Econometrics, Game Theory and Mathematical Economics

Frontmatter

Aggregate Game and International Fishery with Several Countries

In this paper we have been able to derive the closed loop solution for international fishery with several countries engaged in fishing to maximize their total discounted utilities over finite fishing periods. Our international fishery model is a generalized version of the well known model of international fish war between two countries. Recognizing that at each stage of maximization, the equilibrium conditions are those of aggregate games, we have derived rather easily the optimal harvesting rates for the first period for any length of harvesting periods, which enables us to determine the optimal harvesting rates for all subsequent periods.

Koji Okuguchi

A Centrist Poverty Index

Gerhard Kockläuner

Does a Market Sensitive Price Strategy Pay Off in an Oligopoly Market Disturbed by Competitors Without Any Concept?

We investigate the performance of four price strategies in a heterogeneous closed oligopoly with three firms: overhead calculations, target pricing, discount prices and random prices. Using simulation we try to find out, whether market sensitive prices are more successful than others.

Vera Hofer, Klaus Ladner

Order Stable Solutions for Two-sided Matching Problems

We concern the problem of matching the agents from two disjoint sets, such that the agents from the first set have preferences over the agents from the second set and vice versa. Typical problems of this sort are: college admissions problem, matching workers with firms, men with women (in a matrimonial agency) and so on. Classical approach to this problem comes from Gale and Shapley (1962). Recently, a far reaching generalization of Gale-Shapley approach was proposed by Alkan and Gale (2003). In our paper we present another generalization of the Gale-Shapley method, in which we use different concept of stability than the one in Alkan and Gale (the so-called order stability). We show that in some cases the order-stable solutions may be treated as more “fair” than in the Alkan and Gale’s approach. We formulate conditions under which the generalized Gale-Shapley algorithm leads to order-stable and optimal solutions and prove that these conditions are independent.

Zbigniew Switalski

Data Mining for Big Data Macroeconomic Forecasting: A Complementary Approach to Factor Models

Against the background that methods for efficient use of big data sets become increasingly important in applied macroeconomic forecasting literature we presented a forecast model selection approach based on a GA which tries to overcome problems of alternative quantitative methods, e.g., factor analysis and artificial neural networks. The need for new methods is caused by using big data sets for which the use of GAs (as a typical data mining method) seems to be appropriate. Starting from a big data set with typical macroeconomic variables such as German leading indicators and key indicators our goal was to make forecasts for the German industrial production, a long maturity bond, inflation and unemployment. We employed a GA to optimize forecast models. Our results meet all forecasting requirements and stress the advantages of our approach as opposed to alternative methods.

Bernd Brandl, Christian Keber, Matthias G. Schuster

Dominance and Equilibria in the Path Player Game

This paper investigates the relation between Nash equilibria and non-dominated solutions in a special class of games, namely

path player games

. Nash equilibria are situations in a game where none of the players is able to obtain a better outcome by himself. On the other hand, a situation is

non-dominated

if there does not exist a situation which is really better for one of the players, and at least the same for all others. We provide two classes of path player games in which each non-dominated situation is a Nash equilibrium, and one class in which also the reverse is true.

Anita Schöbel, Silvia Schwarze

Exact Solution to a Class of Stochastic Resource Extraction Problems

In this paper, a class of resource extraction problems involving stochastic dynamics and randomly fluctuating non-autonomous payoffs are developed. An empirically meaningful theory of optimization must therefore incorporate uncertainty in an appropriate manner. The introduction of this stochastic specification lead to a novel approach to solve dynamic problems in terms of properties and solution concepts not explored in the literature before. Exact solution to this stochastically complicated problem is presented. Computer simulations are provided. The analysis could be applied to various practical problems involving complex uncertainties.

Sum T. S. Cheng, David W. K. Yeung

Investment Attraction and Tax Reform: a Stochastic Model

We study a model of the behavior of a potential investor (under risk and uncertainty) who wishes to invest in a project of creating a new enterprise and chooses an investment time (timing problem). This model takes the tax environment exhaustively into account. An optimal rule of investment and its dependence on parameters of tax system are obtained. Investigation is based on solving an optimal stopping problem for two-dimensional geometric Brownian motion. We apply Feinmann-Kac formula and variational inequalities as basic methods for deriving the closed-form formulas for optimal investment time and expected tax revenues from future enterprise into budgets of different levels. Based on those formulas, an analysis of the Russian reform of corporate profit taxation (2002) is undertaken, as well as of the tax cuts in VAT (2004) and Unified Social Tax (UST) Rates (2005).

Vadim I. Arkin, Alexander D. Slastnikov, Svetlana V. Arkina

Bayesian Versus Maximum Likelihood Estimation of Term Structure Models Driven by Latent Diffusions

Manfred Frühwirth, Paul Schneider, Leopold Sögner

Exit in Duopoly Under Uncertainty and Incomplete Information

We have shown, by assuming for simplicity that market uncertainty is lower, that in the incomplete information model, there is reversal of exit order in spite of the exclusion of gap equilibrium. Therefore, equilibrium is influenced not only by market uncertainty but also by uncertainty of information about the competitor.

While we assume that the strategy is a continuous and increasing function, there may be a more natural assumption. Also, considering constraint of the distribution function may ensure the uniqueness of the best response.

Makoto Goto, Takahiro Ono

Real Option Approach on Implementation of Wind-diesel Hybrid Generators

Hideki Honda, Makoto Goto, Takahiro Ono

e-Business and Computer Sciences

Frontmatter

Mobile Dienste zum Terminmanagement bei Geschäftsprozessen mit Kundenkontakt

Mario Hopp, Anastasia Meletiadou, J. Felix Hampe

Biometrische Absicherung von Web-Applikationen mit BioW3

Götz Botterweck, Sven Westenberg, J. Felix Hampe

Performance-Measurement- und Analyse- Konzepte im Hochschulcontrolling

Jonas Rommelspacher, Lars Burmester, Matthias Goeken

Risikoanalyse und Auswahl von Maßnahmen zur Gewährleistung der IT-Sicherheit

Zur Gewährleistung der IT-Sicherheit in einem Unternehmen sind zunächst die Anforderungen zu spezifizieren, der erreichte Sicherheitsstand zu beurteilen und anschließend diejenigen Sicherheitsmaßnahmen zu ermitteln, deren Umsetzung eine Optimierung des Sicherheitsniveaus bewirkt. Wurden im Rahmen der Schutzbedarfsfeststellung IT-Komponenten mit hohem oder sehr hohem Schutzbedarf identifiziert, so sind zusätzliche Analysen zur Einschätzung der Risiken erforderlich. Mit diesem Beitrag wird eine Methode vorgestellt, wie zum einen das Risiko einzelner IT-Komponenten evaluiert werden kann und zum anderen konkrete Maßnahmen hinsichtlich ihres Beitrags zur Steigerung des Sicherheitsniveaus eines Unternehmens bewertet werden können. Dies schafft die Basis für die Auswahl optimaler Maßnahmen zur Gewährleistung der ITSicherheit. Die Ermittlung des Risikos und die Auswahl der Maßnahmen unter gegebenen Restriktionen werden mit einem auf der Fuzzy-Sets-Theorie basierenden Ansatz durchgeführt.

Brigitte Werners, Philipp Klempt

m-Parking - Mobile Parking Payment Systems in Europa

Mobile Bezahlsysteme im Rahmen urbaner Parkraumbewirtschaftung stellen eine alternative Anwendung des eBusiness dar und finden zunehmend Verbreitung und Akzeptanz in Europa. Mobile Parkgebührenbezahlung über In-Vehicle devices, anwählbare Dialling a Pay and Display Maschinen und Handyparksysteme werden im vorliegenden Beitrag hinsichtlich ihres Einsatzes in Europa im überblick präsentiert; ferner werden die Vor- und Nachteile der mobilen Bezahlsysteme jeweils aus der Sicht der Anwender und aus der Sicht der Betreiber gegenübergestellt. Der Fokus des Beitrags liegt auf einer detaillierten Analyse unterschiedlicher Handyparksysteme in Europa. Anhand geeigneter Kriterien, wie Technologieoptionen, Registrierungsmöglichkeiten, Abrechnungsalternativen, Kontoführung, Fahrzeugerkennung, Kontrollmechanismen, Tourismusvertr äglichkeit und Zusatzdienste, wird ein systematischer Vergleich von Handyparksystemen durchgeführt.

Christine Strauß, Melitta Urbanek, Gernot Wörther

Sustainable Systems

Frontmatter

Energieorientierte Maschinenbelegungsplanung auf Basis evolutionärer Algorithmen

Ziel des vorliegenden Beitrages ist es, die ökonomischen Einsparpotentiale einer

energieorientierten Maschinenbelegungsplanung

bei diskontinuierlichen Produktionsprozessen anhand eines Beispiels aus der Textilindustrie aufzuzeigen. Dazu wird das vorliegende Planungsproblem als

resource levelling problem

abgebildet. Der entwickelte, heuristische Lösungsansatz beruht auf einem

evolutionären Algorithmus

.

Markus Rager, Axel Tuma, Jürgen Friedl

Multi Objective Pinch Analysis (MOPA) Using PROMETHEE to Evaluate Resource Efficiency

Process optimisation on the basis of detailed process characteristics requires the simultaneous consideration of different mass and energy flows and leads to a multi-criteria problem. Different technological options can be compared based on targets calculated by pinch analyses and further criteria. The approach is applied to a case study on bicycle coating.

Hannes Schollenberger, Martin Treitz, Jutta Geldermann, Otto Rentz

An Emission Analysis on Toxic Substances (SPM and NOx) from Transportation Network System in Tokyo of Japan

Recent years, the increases in toxic substances of NO

x

and/or SPM (Suspended Particulate Matter) from vehicles come to be serious problem. In this paper, we estimated the concentrations of SPM and NO

x

using a traffic flow model. This model has a characteristic of which the traffic volume in each link and the average speed can be decided by solving the problem on the travel time minimization. We also considered the traffic congestions and/or the toll roads in the model, and these effects were reflected to it by converting the time functions. About the correlation between the traffic volume in our model and the real volume, we obtained the correlation coefficient of 0.74. Simultaneously, we got the result that the concentration of NO

x

was approximately 70 to 230 ppb. That of SPM was approximately 40 to 100 µg/m

3

.

Kiyoshi Dowaki, Kouichiro Yoshiya, Shunsuke Mori

Planning and Evaluation of Sustainable Reverse Logistics Systems

Different alternatives exist for installation of scrap treatment systems in order to comply with the German law on discarded electronic equipment. Thus, the aim of this contribution is to compare various treatment alternatives considering economic but also ecological, technical, infrastructural, and social objectives. The MADM-method PROMETHEE is used for the evaluation of these systems. Since many relevant evaluation attributes depend on short-term decisions within a given infrastructure, these decisions are anticipated based on activity based optimization models. Depending on the operation of the treatment systems, either an economic efficient solution applying a LP-model or a sustainable solution applying Weighted Goal Programming (WGP) is calculated.

Grit Walther, Eberhard Schmid, Sanne Kramer, Thomas Spengler

Revenue Management

Frontmatter

Simultaneous Dynamic Pricing and Lot-sizing Decision for a Discrete Number of Price Variations

We investigate the impact of a dynamic pricing strategy on the economic ordering decision where a discrete number of price changes within each order cycle is allowed. Customer reaction to prices is modelled by a linear price response function and the ordering process is subject to variable procurement cost and setup cost. Inventories are subject to holding cost. The objective is to maximize average profit by choosing the optimal lot-size and pricing strategy.

Sandra Transchel, Stefan Minner

Optimal Fares for Public Transport

The

fare planning problem

for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a discrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.

Ralf Borndörfer, Marika Neumann, Marc E. Pfetsch

Auswirkungen eines kontinuierlichen Fleet Assignment Prozesses

Durch die Simulation eines Revenue Management Systems wie es bei Fluggesellschaften in der Praxis eingesetzt wird, konnte ein positiver Erlöseffekt für einen kontinuierlichen Fleet Assignment Prozess nachgewiesen werden. Die Realisierung eines Großteiles des Potenzials bis drei Wochen vor Abflug ist operationell umsetzbar.

Die Vernachlässigung von Gruppenbuchungen, No-Shows und Stornierungen in den Nachfragedaten stellt eine wesentliche Vereinfachung der Realität dar. Deren Abbildung würde jedoch den Prognosefehler erhöhen und sich damit eher positiv auf das Potenzial des Fleet Assignment auswirken. Die Ausdehnung des betrachteten Netzwerkes auf einen gesamten Tag mit den rotationellen Verknüpfungen der Flugzeuge stellt eine weitere Herausforderung dar.

Michael Frank, Martin Friedemann, Michael Mederer, Anika Schröder

Marketing

Frontmatter

Monotonic Spline Regression to Estimate Promotional Price Effects: A Comparison to Benchmark Parametric Models

Andreas Brezger, Winfried J. Steiner

Robust Preference Measurement A Simulation Study of Erroneous and Ambiguous Judgement’s Impact on AHP and Conjoint Analysis

Despite the recent methodological progress to unburden respondents in preference analysis the quality of consumers’ judgements is fundamental for marketing research results. Surprisingly, the impact of ambiguous and erroneous judgments given by the respondents is widely neglected in the marketing literature. In this paper we compare the Analytic Hierarchy Process and Conjoint Analysis with respect to the impact of random errors as well as ambiguities in preference statements by means of Monte Carlo simulation studies. Referring to Thurstone’s law of comparative judgements, we demonstrate the superior robustness of the Analytic Hierarchy Process in dealing with these kinds of perturbing effects.

Sören W. Scholz, Martin Meißner, Ralf Wagner

Improving the Predictive Validity of Quality Function Deployment by Conjoint Analysis: A Monte Carlo Comparison

The “new” CA based approach for QFD shows a number of advantages in comparison to the traditional approach. PA importances as well as PC influences on PAs are measured “conjoint” resp. simultaneously. Furthermore, the calculated weights are more precise (real valued instead of 0-, 1-, 3-, or 9-values) which resulted in a higher predictive validity. The Monte Carlo comparison has shown a clear superiority in a huge variety of simulated empirical settings.

Daniel Baier, Michael Brusch

System Dynamics Based Prediction of New Product Diffusion: An Evaluation

System Dynamics (SD) is a methodology that can be used for analysing and understanding complex feedback systems. Influencing factors, time delays as well as dynamic relations between factors and effects can be assumed and used for simulations and the development of strategies. Whereas the aim of SD models is the better understanding of the relationship between underlying structure and behaviour of the feedback system, it can also — at least in principal — be used for forecasting. This paper analyses this application field by using real and generated data on new product diffusions in a calibration — validation — setting.

Sabine Schmidt, Daniel Baier

Managerial Accounting

Frontmatter

Portfolio Optimization as a Tool for Knowledge Management

The method and the tool give managers a good overview of how an optimal portfolio could be composed given the projects they gave as input. The tool is a decision support system and enables a solid starting point of reasoning and discussion about the optimal portfolios in a given situation. Many questions are still left open for future research: The tool was applied in a medium sized organization: can it be used in larger companies running multiple portfolios? Which people should be included to fully utilize the potential of the tool?

Hennie A. M. Daniels, Martin T. Smits

Berücksichtigung nicht-finanzieller Aspekte im Rahmen eines Entscheidungsmodells für Zwecke der Unternehmenssteuerung

Es wird eine Methode vorgestellt, die es ermöglicht nicht-finanzielle Zusammenhänge bei der Entwicklung von Entscheidungsmodellen zur unternehmensübergreifenden Koordination zu berücksichtigen. Das untersuchte Problem entsteht durch die Forderung, auch nicht-finanzielle Ziele im Rahmen von quantitativen Zielsystemen zu berücksichtigen. Die vorgeschlagene Methode wird auf den Bereich Absatz exemplarisch angewandt.

Dirk Heyne

Wirtschaftliche Folgen von Verträgen — eine Simulationsstudie

Markus Spiekermann

Tourism, Entertainment and Sports

Frontmatter

Identifying Segments of a Domestic Tourism Market by Means of Data Mining

This paper helps to analyse a typical problem seen in the marketing systems of firms in tourism industry. The problem here is the difficulty in determining the market segments for an optimal customer management. In this work, data mining is used as a decision support tool in order to extract previously unknown patterns and ultimately comprehensible information from large databases which traditional statistical tools can not extract. The research is conducted in Bursa, the fourth biggest city of Turkey. The multi-dimensional analysis of this domestic market is very important for foreign hotel investors, tour operators and travel agencies in their investment, marketing and management strategies. For this multi-dimensional analysis, visual and robust data mining software Clementine 8.1 is used for the classification task of data mining in order to determine the market segments for optimal customer management.

Gül Gökay Emel, Çağatan Taşkın

Scheduling and Project Management

Frontmatter

Scheduling Tests in Automotive R&D Projects

In order to reduce testing costs in automotive R&D projects, we introduce an approach to schedule necessary tests such that the number of used experimental vehicles is minimized. Based on a multi-mode resource-constrained project scheduling model with cumulative resources, we propose a MIP formulation, which is solvable for small problem instances. A priority-rule based method serves to solve large problem instances. Finally, we present preliminary computational results.

Jan-Hendrik Bartels, Jürgen Zimmermann

Cyclic Scheduling Problems with Linear Precedences and Resource Constraints

Peter Brucker, Thomas Kampmeyer

Ein System zur Lösung multikriterieller Probleme der Ablaufplanung

Der vorliegende Artikel stellte ein System zur Lösung multikriterieller Probleme in der Ablaufplanung vor. Hierzu wurden heuristische Problemlösungskomponenten entwickelt, implementiert und erfolgreich auf Testprobleme angewendet. Ein lokales Suchverfahren auf der Grundlage wechselnder Nachbarschaftsdefinitionen wurde verschiedenen Evolutionären Algorithmen gegenübergestellt. Im Ergebnis erweist sich für die untersuchten Probleme die Konzeption des MOVNS den EA als überlegen.

Die Auswahl einer für einen Entscheidungsträger „optimalen“ Alternative wird durch die Integration eines interaktiven Verfahrens in das Gesamtsystem ermöglicht, welches direkt auf den Ergebnissen der Optimierungsläufe aufbaut. Der vorgestellte Lösungsansatz hat somit den Vorteil, ohne Präferenzinformationen des Entscheidungsträgers erste Ergebnisse erzielen zu können. Diese werden vielmehr in einem weiteren Schritt sukzessive in die Problemlösung integriert.

Denkbar und für weitere Untersuchungen geeignet ist in diesem Zusammenhang die Frage, wie etwaige Präferenzinformationen vorab in den Optimierungsprozess einfließen können. Dies ist insbesondere dann von Interesse, wenn diese nur partiell vorliegen oder nur unscharf beschrieben werden können.

Martin Josef Geiger

On a Single Machine Due Date Assignment and Scheduling Problem with the Rate-Modifying Activity

In this paper we consider single machine common due date assignment and scheduling problem. The objective is to minimize the total weighted sum of earliness, tardiness and due date costs. There exists a possibility to perform some action (rate-modifying activity) to change processing times of the jobs following this activity. Thus, placing the rate-modifying activity to some position in the schedule can decrease the objective function value. We consider several properties of the problem which in some cases can reduce the complexity of the solution algorithm.

Valery S. Gordon, Alexander A. Tarasevich

Primal-Dual Combined with Constraint Propagation for Solving RCPSPWET

András Kéri, Tamás Kis

Ein Ameisenalgorithmus für die ressourcenbeschränkte Projektplanung mit Zeitfenstern und Kalendern

Thomas Knechtel, Jens Peter Kempkes

The Flow Shop Problem with Random Operation Processing Times

We consider the classical flow shop problem with

m

machines,

n

jobs and the minimum makespan objective. The problem is treated in stochastic formulation, where all operation processing times are random variables with distribution from a given class

F

. We present a polynomial time algorithm with absolute performance guarantee

C

max

(

S

) −

L

≤ 1.5(

m

− 1)

p

+

o

(1) that holds

with high probability

(Frieze, 1998) for

n

→ ∞, where

L

is a trivial lower bound on the optimum (equal to the maximum machine load) and

p

is the maximum operation processing time. Class

F

includes distributions with regularly varying tails. The algorithm presented is based on a new algorithm for the compact vector summation problem and constructs a permutation schedule. The new absolute guarantee is superior to the best-known absolute guarantee for the considered problem (

C

max

(

S

) −

L

≤ (

m

− 1)(

m

− 2 + 1/(

m

− 2))

p

; Sevastyanov, 1995) that holds for all possible inputs of the flow shop problem.

Roman A. Koryakin, Sergey V. Sevastyanov

A Heuristic Solution for a Driver-Vehicle Scheduling Problem

A driver-vehicle scheduling problem in a limousines rental company is studied. Given a set of trip demands to be covered, the goal is to find a driver-vehicle schedule that covers as many as possible of the required demands while satisfying a set of imperative constraints and optimizing several cost objectives. A formulation of the problem is given and a solution approach using local search is developed.

Benoît Laurent, Valérie Guihaire, Jin-Kao Hao

Scheduling Jobs with Uncertain Parameters: Analysis of Research Directions

Yakov Shafransky

Job-Shop Scheduling by GA. A New Crossover Operator

The new distance measure between job-shop solutions, based on Euclidean measure, has been proposed. The significant positive correlation of the proposed measure with its suitable version based on the Kendall’s tau measure has been revealed. By applying this measure, a new, easy tunable, crossover quasi-operator for the genetic approach is designed. The genetic algorithm, equipped with the new operator, has been applied to the job-shop scheduling problem with the sum of job completion times criterion. Results provided by the algorithm, compared with the best results known in the literature, confirm superiority of the proposed method.

Czesław Smutnicki, Adam Tyński

Robotic Cells: Configurations, Conjectures and Cycle Functions

Robotic cells consist of a flow-shop with a circular layout and a single transporter, a robot, for the material handling. A single part is to be produced and the objective is to minimize the production rate. Different cell configurations have been studied, depending on the travel times of the empty robot: additive, constant or just triangular.

A

k

-cycle is a production cycle where exactly

k

parts enter and leave the system. Consider the set

S

K

of all

k

-cycles up to size

K

where

S

K

contains, for every instance, an optimal solution and

K

is minimal. The cycle function

K

depends on the cell configuration and the number of machines. Some of these functions are known and there are conjectures about others. We give new results invalidating in particular the so-called Agnetis’ Conjecture for the classical robotic cell configuration.

Nadia Brauner, Gerd Finke

Technology and Innovation

Frontmatter

Robot Task Planning for Laser Remote Welding

Up to now, no commercial offline programming system for robot-assisted laser remote welding exists. The Generalized Traveling Salesman Problem seems to model sequential remote welding jobs with sufficient accuracy, if adequate constraints are taken into account. Robot kinematics based on homogeneous transforms was found to be a simple tool used throughout system abstraction. It could be proven that modeling and subsequent optimization results in shorter cycle times than for robot paths obtained by empirical knowledge and intuiton. Further research options are, for instance, multiple robot facilities and coupled axes systems.

Jannis Stemmann, Richard Zunke

Technologischer Fortschritt in der deutschen Bankenwirtschaft

In dieser Arbeit wurde das Produktivitätswachstum von Genossenschaftsbanken mittels des Malmquistindex untersucht. Der besondere Beitrag dieser Arbeit liegt in einer Separierung des Malmquistindex auf eine managementbedingte Effizienzverbesserung und auf eine technologisch bedingte Verschiebung der Effizienzgrenze. Neben einer Messung der Produktivität wurde ebenfalls ein positiver Zusammenhang zwischen IT-Nutzung und dem technologischen Fortschritt festgestellt. Im letzten Untersuchungsschritt wurde die Effizienzgrenze von Onlinebanken gegenüber der Effizienzgrenze herkömmlicher Geno verglichen. Im Durchschnitt dominieren Onlinebanken die Geno.

A. Varmaz, Th. Poddig

Consistency Matrices Within Scenario Technique: An Empirical Investigation

For this paper consistency matrices were analysed. Those consistency matrices were identified as being different, three clusters have been founded. These clusters differ in the distributions of the evaluated values in matrix for triangular relationships.

To come to a semi-automatic algorithm for estimation of consistency values two major implications may be drawn from this empirical investigation:

1)

According to the three cluster solution three different algorithms (or one algorithm with three different parameter settings) are needed. The authors are working with fuzzy rules for that goal.

2)

To start an algorithm for a semi-automatic matrix filling in it has to be decided to which of the three clusters the only partially filled input matrix should be assigned. Therefore, experiments with discriminant analysis and case-based reasoning are conducted.

Ewa Dönitz, Martin G. Möhrle

Distributed Neurosimulation

Distributed computing allows to combine the computing power of miscellaneous computers. The computers may be at different locations as long as they are connected via a network, e. g. the Internet or an intranet. In this paper the development of a distributed computing version of the neurosimulator FAUN (

F

ast

A

pproximation with

U

niversal Neural

N

etworks) is described. This offers the opportunity to use free computing resources, e. g. of a student and staff computer cluster. An easy to install client is part of the development work. The combined computation power is necessary for, e. g., fast forecasting or fast simulation problems to be solved with FAUN which would otherwise take hours or days on a single processor computer. Problems which computation time can be shortened significantly by distributed computing with FAUN include, but are not limited to, dynamic games, robust optimal reentry guidance of a space shuttle and currency forecasting.

Hans-Jörg v. Mettenheim, Michael H. Breitner

Decision Theory

Frontmatter

Multi-Criteria Decision Support and Uncertainty Handling, Propagation and Visualisation for Emergency and Remediation Management

The real-time online decision support system RODOS provides support throughout all phases of a nuclear or radiological emergency in Europe. The multicriteria decision support tool Web-HIPRE has been integrated into RODOS for a transparent evaluation of long-term measures, taking into account the preferences of a decision making team. However, a decision making process in practice is subject to various sources of uncertainty. This paper describes a Monte Carlo approach to consistently model and propagate the uncertainties within the RODOS system, including Web-HIPRE, aiming at comprehensibly visualising and communicating the uncertainties associated with the results from the decision analysis.

Jutta Geldermann, Valentin Bertsch, Otto Rentz

Interactive Decision Support Based on Multiobjective Evolutionary Algorithms

Although, we do not yet have practical experiences with using the new approach for multicriteria decision support and optimization, it is appealing because the interaction between navigation interface and MOEA solves two problems at the same time. First, the MOEA provides a new and effective means for feeding the navigtion interface with data on solutions to a hard-to-solve multiobjective optimization problem in an on-line fashion. The usage of solution interpolation or a database resulting from a computationally expensive apriori calculation of solutions can be avoided, at least in part.

Secondly, information from the navigation interface allows the MOEA to concentrate on a preferable subset of solutions which is frequently much smaller than the whole set of Pareto-optimal solutions. Thus, the computational effort of the MOEA may decrease drastically.

The asynchronous concept of the communication between user interface and MOEA avoids waiting times both for the human user and for the computer. A user has still the possibility to let the MOEA run autonomously for a longer time (or until a stopping criterion for the MOEA is reached) and then navigate through the final result of the algorithm. Thus, complexity of user input and frequency may be kept to an acceptable amount.

Thomas Hanne

Using a Combination of Weighting Methods in Multiattribute Decision-Making

In this paper we introduce a preliminary approach for a weighting method that is intended to overcome possible biases detected in traditional weighting methods. The procedure is based on a combined application of several methods,

SWING weighting, TRADE-OFFS weighting

or

Direct point allocation

. It benefits from the value tree and the propagation of attribute weights through the tree to perform consistency checks and admits imprecision concerning the DM responses, whcih leads to imprecise local and attribute weights. However, the possible inclusion of other weighting methods in the process and the analysis of associated biases still needs to be analyzed.

Antonio Jiménez, Sixto Ríos-Insua, Alfonso Mateos

Gremienentscheidungen bei partiellen Präferenzordnungen

Im Rahmen der individuellen Entscheidungstheorie finden partielle Präferenzordnungen immer stärker Beachtung. Fehlt die Angabe, ob ein Entscheider eine Alternative strikt präferiert oder indifferent ist, so mag dies schlicht daran liegen, dass kein Vergleich stattgefunden hat. Es ist aber auch möglich, dass nachMeinung des Entscheiders mit den zur Verfügung stehenden Informationen oder unter den gegebenen Rahmenbedingungen kein Vergleich durchgeführt werden kann. Letztere Auffassung sollte ein Entscheider auch bei Entscheidungen, die von einem Gremium getragen werden, einbringen können. Regeln zur paarweisen Aggregation individueller Präferenzrelationen erlauben die Interpretation fehlender Präferenzen. Wie im Falle vollständiger Präferenzordnungen lässt sich auch hier die Transitivität der kollektiven Präferenzordnung durch ein speziell erweitertes Eingipfligkeitskriterium gewährleisten.

Eva Ponick

The Impact of Preference Structures in Multi-Issue Negotiations — an Empirical Analysis

Most of the hypotheses we have tested seem to be rather straightforward: when negotiators consider an attribute to be more important, it is quite natural that they negotiate tougher regarding this attribute and obtain better outcomes than negotiators who do not really care about an attribute.

The important conclusion of this paper is that the multi-attribute utility functions elicited in Inspire really reflect these attitudes of negotiators. Even in cases where the utility functions contradict the case descriptions, e.g. when a buyer has a monotonically increasing utility function for price and thus assigns higher utility to a higher price, the actual behavior reflects the utility function, and not the more natural case description. Thus we can conclude that multi-attribute utility functions as used in Inspire can really capture the preferences of negotiators, even when they seem to be quite odd.

This is an important and positive message concerning the possibility to use analytical tools for negotiation support. When the preferences which really guide a negotiator’s behavior can be captured with sufficient precision in a utility function, such a utility function can also be used to provide substantial and useful advise to a negotiator.

Rudolf Vetschera

Applied Probability

Frontmatter

Stochastic Analysis of the Traffic Confluence at the Crossing of a Major and a Minor Road

We present a stochastic model for the traffic situation at a crossing of a major and a minor road. Afterwards, we give an overview of two recent results for this model. First, the distribution of the waiting time for a large gap is given. This might also have applications in other settings, where one has to wait for a large gap to occur in a Poisson process. The second result shows, that the queue length on the minor road is either a V-ergodic Markov chain or it is transient. This justifies the estimation of the stationary distribution by the time mean of the queue length in a computer simulation.

Frank Recker

Decomposition in Multistage Stochastic Programs with Individual Probability Constraints

Vlasta Kaňková

Algorithmic Procedures for Mean Variance Optimality in Markov Decision Chains

Karel Sladký, Milan Sitař

On State Space Truncation of Finite Jackson Networks

An error bound result is provided for the truncation of a finite Jackson network from which both a computational and analytic error bound can be concluded. The results are illustrated for a special application of a cellular mobile communication network.

Nico M. van Dijk

Numerical Method for the Single-Server Bulk-Service Queuing System with Variable Service Capacity, M/Gy/1, with Discretized Service Time Probability Distribution

Some of the most relevant papers tackling bulk service queueing systems with random service capacity were briefly described, through the analysis of the results given it was found that other authors solutions are difficult to apply. The solution method presented here does not require to fit a theoretical probability distribution for service time, but there is a need to find a discrete distribution matching at least the first two moments of the empirical service time distribution. Recursive numerical convolution of probability vectors must be carried out on a computer program, which is easy to implement. Numerical results are accurate enough for practical purposes.

An important advantage this model has among other approximation queueing model, such as those analysing the system at phase epochs, is that the system is observed at service epochs, having in consequence a substantial saving in computer running time.

MejÍa-Téllez Juan

Worst-case VaR and CVaR

The main goal of this paper is to derive and compare values of worst-case VaR and CVaR under different type of information on distribution of random parameter. To this purpose we exploit results from moment problem theory and apply upper bound of loss probability of univariate random variable with special properties, given expected value and variance. Subsequently, we suppose that except the first two moments of the distributions, we know further characteristics of the class of distributions. We assume symmetry and/or unimodality. The bounds are also illustrated on the case of interbank exchange rate.

Jana Čerbáková
Weitere Informationen

Premium Partner

    Bildnachweise