Operations Research Proceedings 2004

Im Rahmen einer Zusammenarbeit mit der Firma Stahlwerk Ergste-Westig GmbH, einem Unternehmen der ZAPP AG, wurde ein Verfahren zur Lösung eines 1.5-dimensionalen Verschnittproblems entwickelt und prototypisch implementiert. Das Problem zeichnet sich durch einen begrenzten Lagerbestand mit sehr heterogenem Sortiment und zusätzlichen Nebenbedingungen zur Materialverwendung aus. Es wird durch ein lineares ganzzahliges Modell abgebildet und mittels einer Branch-and-Cut Strategie unter Einsatz der MIP-Solver MOPS und CPLEX gelöst. Dabei wird durch ein um die Berücksichtigung von Range-Bedingungen erweitertes MOPS IP-Preprocessing eine entscheidende Verbesserung der Lösungsqualität und Verkürzung der Rechenzeit erreicht. Das implementierte Entscheidungsunterstützungssystem konnte die realen Probleminstanzen effizient und im Sinne des Unternehmens lösen und erzielte in den durchgeführten Vergleichsrechnungen ein Reduzierungspotential für den Verschnitt von etwa 30% zum bisherigen Vorgehen. Unter Verwendung des Systems ist neben der Ersparnis durch die Verschnittreduzierung auch ein deutliches Einsparpotential an personellen Ressourcen durch den im Vergleich zur manuellen Disposition geringen Zeitbedarf vorhanden.

We present an algorithm for the problem of routing Automated Guided Vehicles (AGVs) in an automated logistic system. The algorithm avoids collisions, deadlocks and livelocks already at the time of route computation (conflict-free routing). After a preprocessing step the real-time computation for each request consists of the determination of a shortest path with time-windows and a following readjustment of these time-windows. Both is done in polynomial-time. Using goal-oriented search we get computation times which are appropriate for real-time routing. Additionally, in comparison to a static routing approach, used in Container Terminal Altenwerder (CTA) at Hamburg Harbour, our algorithm had an explicit advantage.

All-optical

telecommunication networks allow for switching connections by

lightpaths

which can pass several network links without any opto-electronic conversion. Upon arrival of a connection request, it must be decided online, i.e., without knowledge of future requests, if it is accepted and in that case on which lightpaths the connection is routed. This

online problem

with the goal of maximizing the total profit gained by accepted requests is called

Dynamic Singleclass Call Admission Problem

(Dsca). We present existing and new algorithms for Dsca as well as their theoretical and practical evaluation.

In this paper we discuss the value of accurate inventory information for distribution planning purposes in a reverse logistics system. Three levels of information are introduced and the value is assessed in a simulation loop. For every planning period the operational vehicle routing problem is solved to optimality by route enumeration and set partitioning. Extensive sensitivity analysis is performed and discussed to analyze the factors that influence the value of accurate inventory information for reverse distribution planning. Network density appears to be one of the main determinants.

We consider a production inventory problem under periodic review with stochastic demand and stochastically proportional yield. Defective products (i.e. the yield loss) arising from the unreliable production process can be temporarily stored in an inventory and passed through a rework process. Rework is completely reliable and brings defective products up to the same quality level as new ones, so that they can be used for demand fulfilment. We focus on the application of linear heuristic policies similar to those emerging from MRP application, and develop simple expressions for the computation of policy parameters. Results of a numerical study indicate that the heuristic approach performs quite well.

Remanufacturing is the most valuable product recovery option since here the value added to the product can be obtained. The goal of this contribution is to develop an instrument which supports decision makers in their considerations about implementing a remanufacturing strategy. The framework is built on a two-stage proceeding, where in the first step an approach for modeling this strategic decision process is presented. In the second step, the contribution aims to show how to evaluate alternative decisions economically by developing a life cycle model for remanufacturing and calculating the life cycle costs.

We investigate the interest of migrating from a call center where all agents are pooled and customers are treated indifferently by any agent, towards a call center where customers are grouped into clusters with dedicated teams of agents. Each cluster will be called a portfolio. Customers of a same portfolio are always served by an agent of the corresponding team. There is no specialization involved in this organization in the sense that all customer portfolios as well as all agents teams have (statistically) identical behaviors. The purpose of this paper is to investigate how the benefits of moving to this new organization in terms of the management of the workforce can outweigh its drawback that comes from the increasing of variability.

In the production of perishable products such as dairy, meat, or bakery goods, the consideration of shelf life in production planning is of particular importance. Retail customers with relatively low inventory turns can benefit significantly from longer product shelf life as wastage and out-of-stock rates decrease. However, in today’s production planning and control systems shelf life issues with regard to specific products or customers are seldom taken into account. Therefore the objective of this paper is to pay attention to these issues. The way to do that is by means of optimization models in which shelf life aspects are integrated into operational production planning and scheduling functions. Specifically we make use of so-called Mixed Integer Linear Programming (MILP) models. Our research is based on an industrial case study of yogurt production. Relying on the principle of block planning, an MILP model for weekly production planning is presented that is based on a combination of a discrete and a continuous time representation. Batch sizing and scheduling of numerous recipes and products on several packaging lines are considered in the model. Overnight production and, hence, the necessity for identifying two different shelf life values for the same batch is also included in the model formulation. Numerical experiments show that near-optimal solutions can be obtained within a reasonable computational time. Finally, the proposed MILP model can be adapted to cover specific features arising in other fresh food industries.

We consider a semiconductor manufacturing facility with multiple products and associated routes, single servers and batch servers, job class dependant service times and external arrivals. The system is modelled as an open queueing network. The aim is to optimize routing such that cycle time constrained capacity is maximized and can be checked in reasonable computation time. We use a decomposition approach based on the connected components of a properly defined fab graph. Taking into consideration arrival rate vectors and service time matrices the routing problem for the network is formulated as a Quadratic Programming Problem (QP) involving averages and variances. The strategy for use of the manifold routing options as they typically occur in semiconductor manufacturing is to distribute load in a way such that each connected component, also called closed machine set (CMS), approaches heavy traffic resource pooling behaviour. In the presence of batch servers, mainly in the furnace area of a fab, results for the batch service queue

M/D

[

r, K

]

/1 with threshold server starting policy are combined with a new result for a batch service system with infinitely many job classes and Round Robin service discipline and applied along with the QP solver.

Blood banks produce and store blood products in order to fulfil the uncertain demand at hospitals. Platelet pools are the most expensive and most perishable blood product having a shelf life of only four to six days. Production volumes need to be chosen carefully in order to reduce outdating while keeping the occurrence of shortages low.

We investigate the structure of the optimal production policy by solving a down sized periodic Markov Decision Problem. The optimal production volumes appear to depend on the number of pools on stock and their ages. Simulation results for the optimal

MDP

-policy suggest two rules: the 1

D

and 2

D

rule. Both rules perform quite well. The 2

D

rule performs nearly optimal even if one acknowledges the distinction of multiple and limited compatible blood groups and the uncertainty in the supply by donors.

Die Steuerung der Fertigung von Chips in der Halbleiterindustrie wird aus Vorgabewerten von so genannten Performance-Indikatoren abgeleitet. Kennzahlen der Liefertreue werden dabei als Leistungsgrößen und Plan-Vorgaben verwendet. Um die Wechselwirkungen der Plan-Vorgaben in der internen Supply Chan einer Halbleiterfertigung zu untersuchen, wurde ein zeitdiskretes Modell entwickelt. Die Ergebnisse zeigen, dass sich die einzelnen Leistungs-Vorgaben gegenseitig beeinflussen und somit nicht unabhängig festgelegt werden können.

Our paper is dealing with the Capacitated Stochastic Lot-Sizing Problem. In addition to the usual model assumptions as stochastic demand and manufacturing times, cost for setup, we also consider cost for waiting and lost demand. The goal is to find release and sequencing decisions with minimal expected cost per time unit. To solve the problem we use simulation optimisation, i. e., we combine a simulator with a Parallel Genetic Algorithm. Some numerical examples show the applicability of the proposed approach.

Im folgenden werden flexible Fließproduktionssysteme mit Montagestationen untersucht. An solchen Stationen werden Komponenten von mehreren Zulieferstationen zur Bildung eines neuen Werkstücks zusammengefügt. Das ist die sog. Synchronisationsbedingung. Der Materialfluß ist asynchron. Die Puffer sind beschränkt. Die Bearbeitungszeiten sind beliebig verteilt. Der folgende Beitrag beschreibt ein Verfahren zur Abschätzung der Produktionsrate eines solchen Systems. Hierfür wird ein Dekompositionsansatz verwendet. Die betrachteten 2-Stationen-Subsysteme werden als Warteschlangenmodelle abgebildet, für die die virtuellen Ankunfts- und Bearbeitungsraten sowie die zugehörigen Variationskoeffizienten zu ermitteln sind. Die Approximationsgüte des Verfahrens wird mit einem Simulationsexperiment untersucht.

Supplier selection decisions at the strategic level are focused on strategic items with both a high supply risk and a high profit impact. Therefore, strategic supplier selection decisions have to be long-term orientated considering (i) mutual commitments between the partners involved, (ii) fixed costs upon selection of a new supplier in the form of investment in training, and technology, as well as (iii) significant costs of switching from one supplier to another. Existing approaches of supplier selection neglect the interdependencies in time arising from investment costs of selecting a new supplier and costs of switching from one supplier to another. Moreover, it is assumed that the set of employed suppliers can be changed each period without cost. These shortcomings of current approaches motivates the research presented in this paper. A stochastic dynamic model for supplier selection based on hierarchical planning approaches will be presented. This model enables the evaluation of alternative dynamic supplier selection strategies.

A major problem in modelling and subsequent simulation of process-oriented systems (ProC/B models), is the functional correctness of the model. Therefore a model should be first analysed for its functional correctness before it is analysed by simulation. Petri nets are well suited for model based and state based functional analysis, but are often not adequate or not used for the specification of process models. We present in this paper a transformer for an automatic mapping from ProC/B models onto PNs. The resulting PN-models can be analysed with PN-algorithms and the results from the PN-analysis can be interpreted at the ProC/B level.

Currently, many railway operators are increasing the frequencies of their trains. By condensing the timetable, routing trains becomes increasingly difficult as the chosen routes not only have to meet safety restrictions, but also guarantee some stability if delays occur.

We address the problem of routing trains through railway stations for a given timetable and outline two algorithms. The first algorithm searches for a feasible solution for the train routing problem based on an independent set modeling that is solved using a fixed-point iteration method. The initial solution is then amended by applying the second algorithm in order to increase the time slot of a chosen route, i.e. the time interval during which a train may arrive and find its designated route open. This algorithm is based on a local search optimization scheme.

Results showed that the fixed-point iteration found feasible solutions within minutes even for difficult cases, i.e. tight timetables. Though more time-consuming, the second algorithm allowed the average time slot length to be doubled, thus implying that it is possible to find routings which are more delay-tolerant. This helps to decrease impacts of late trains.

We describe a flexible indirect search procedure which we have applied for solving a special pick-up and delivery vehicle routing problem with time windows. The heuristic is based on an encoding of a solution as a sequence/permutation of tasks, a cheapest insertion decoding procedure, and, a threshold-accepting like local search meta-heuristic.

In many rural areas, the public bus service is demand-oriented: By far the biggest group of customers are pupils who are transported to their schools within certain strict time limits. Usually, all schools start around the same time, which causes a morning peak in the number of deployed buses. However, schools are allowed to change their starting times within some interval. The question is, how to simultanenously rectify the starting times for all schools and bus trips in a certain county so that the number of scheduled buses is minimal. This problem can be formulated as a vehicle routing problem with coupled time windows (VRP-CTW), which is an extension of the vehicle routing problem with time windows (VRP-TW), where additional coupling constraints on the time windows are introduced. We give a mixed-integer programming formulation for VRP-CTW, and present solutions and lower bounds for randomly generated and real-world instances.

Disruption management for airline crew schedules is important for the airline industry, since an increasing amount of disruptions to the regular operations occur frequently. The emphasis of this task is put on quickly obtaining one or more reasonable, at best optimal, recovery solutions from current disruptions, which has to be achieved within an acceptable time period. In this work, we propose a decision support framework that combines exact optimization methods and meta-heuristics for solving real-life practical problems. An exact method, based on a Column Generation type of procedure, is studied and tested, while a dedicated Genetic Algorithm working with a local improvement procedure provides the capability to solve the problem alternatively. Notably, a so-called

strategy mapping

procedure is applied to customize solution methods.

Tail Assignment is the problem of assigning specific aircraft to flights, producing a fully operational, robust schedule which fulfills operational constraints, while minimizing a cost function. The costs are usually related to robustness and quality of the solution, e.g. to penalize short times between flights and reward “crew-friendly” connections. Carmen Systems’ Tail Assignment system utilizes a combination of optimization methods and constraint programming to solve this problem. An interesting aspect of the system is that it can solve several fleet types at once, moving towards an integration of the traditional two-step approach of first solving the Fleet Assignment problem and then Tail Assignment. The article intends to explain some of the methods used.

In der Regel wachsen die Transportkosten auf der letzten Meile mit der Enge des Lieferzeitfensters. Dies stellt insbesondere Anbieter vor ein Problem, die Aussagen über einen präzisen Liefertermin bei Bestellung abgeben müssen, obwohl noch nicht alle zu bedienenden Lieferungen bekannt sind.

Im folgenden Beitrag wird das Problem als D-VRSP-TW-UC-DO modelliert. Motiviert durch die raum-zeitliche Analyse der Solomoninstanzen wird der Begriff der Gleichzeitigkeit als wesentlicher Kostentreiber herausgearbeitet. Anschließend wird ein praxistaugliches Verfahren (ORA) vorgestellt, das es ermöglicht, eine hohe Avisgenauigkeit bei Bestellung zu erlangen. SchlieBlich werden typische Ergebnisse des Verfahrens dargestellt und diskutiert.

This contribution addresses the consideration of time windows in the optimization of multi-commodity network flows. For each node, one interval is specified in which the visitation is allowed. Applications in freight flow consolidation let this problem become interesting. An optimization model is proposed and a construction heuristic is presented. For improving the generated solutions, a genetic algorithm framework including several hill climbing procedures for local optimization, is configured.

We present two different approaches to minimize total delay in signalized fixed-time controlled inner city traffic networks. Firstly, we develop a time discrete model where all calculations are done pathwise and vehicles move on “time trajectories” on their routes. Secondly, an idea by

Gartner, Little

, and

Gabbay

(GLG) is extended to a continuous, linkwise operating model using “Link Performance Functions” to determine delays. Both models are formulated as mixed-integer linear programs and are compared and evaluated by PTV AG’s simulation tool VISSIM 3.70.

For the stochastic flow shop problem with

m

machines,

n

jobs and operation processing times being independent identically distributed random variables, we consider permutation schedules — those in which each machine processes the jobs in the same order. For fixed

m

and increasing

n

, the asymptotic behavior of an arbitrary permutation schedule length is researched. Let

T

be the makespan of that schedule. Considering the maximum machine load

L

as a lower bound of the makespan, we show that for a wide class of operation processing time distributions the average-case ratio

T/L

converges to 1.

Thus, an arbitrary permutation flow shop schedule is asymptotically optimal with

n

→ ∞, and one can construct such schedule in a linear time. The same result is derived for the stochastic assembly line problem with

m

machines and

n

jobs.

We consider a generic workforce scheduling problem, where employees are characterized by qualifications. Given a set of shifts for each day, we have to determine for each employee his working days as well as a specific shift for each working day. The overall objective is to find a set of feasible schedules with respect to hard and soft restrictions. We propose an integer multi-commodity network flow formulation for the problem under consideration and show how branch-and-price can be used to solve this problem.

We consider a single processor scheduling problem with a common due window assignment. Jobs completed within the due window incur no penalty, while other jobs incur either earliness or tardiness penalties. Boundaries of the due window are decision variables. The objective is to minimize the sum of the total weighted earliness, the total weighted tardiness and due window width penalty. This problem is an extension of the classical Weighted Earliness and Tardiness problem (

WET

). We proved that our problem is NP-hard and presented some properties of an optimal solution. To solve the problem we constructed a dynamic programming algorithm and a fully polynomial time approximation scheme. We also presented a polynomial time algorithm for the case with unit job processing times.

Starting with a comprehensive analysis of empirical and theoretical papers on market entry mode choice, as well as by referring to the characteristics of small and medium sized enterprises (SMEs), we develop a new quantitative model that represents SMEs’ choice between joint venture (JV) and wholly owned foreign venture (WOFV). With the help of this model, we deduce some useful propositions for decision makers, both in companies concerned and in economic policy.

This paper introduces a new growing neural network for pattern detection which bears certain resemblances to the growing neural gas network suggested by Pritzke (1995) [2]. However, the algorithm at hand is more parsimonious with respect to the number of parameters to be specified a priori. Thus it is largely autonomous regarding the data-driven construction of the final network topology which unburdens the user significantly. To demonstrate its performance and adaptability the new algorithm is applied to real classification tasks in lifestyle analysis and media usage analysis.

Increasing attention has been devoted in recent years to the firm’s ability to adapt its marketing strategies to a rapidly changing environment. Given that the abundance of news, reports, and announcements found in new electronic environments such as the WWW hampers an extensive manual search, computer-based systems have become important supportive tools for business planning purposes. Several studies investigate the impact of managerial traits on this question, however the potential influence of an inadequate information structure in automatic information-seeking tools is rarely addressed.

In this paper, we examine the effect of the quality of the information structure in automated information-seeking tasks. We use a prototypic system that aims to detect and to evaluate relevant information about financial markets, and systematically contaminate the information structure by index terms referring to an adjacent but different task. Empirical evidence from an experimental evaluation of documents from the Reuters text collection substantiates the relevance of the prior information structure to the automated information search.

Optimizing product lines is the task of planning the joint offer of multiple substitutes concurrently. Actually, this resembles the design of a choice menu where consumers are supposed to choose at most one item from a set of alternatives.

In this paper we model the product line optimization problem by decomposing it into two stages. Product decision is done in the first stage by anticipating possible outcomes of the subsequent (price) stage. This so-called hierarchical decision situation is considered due to uncertainty about consumers’ tastes. Results suggest that substantial increase of expected profit can be drawn from the hierarchical approach.

Within this paper, the energy model PERSEUS-HYDRO and its application to Switzerland with a focus on the possibility to provide long-term electricity prices will be presented. Within this model perfect energy markets are assumed and thus electricity prices can be derived from system-marginal-costs. Main features of the plant dispatch within a system with hydro and thermal power will be shown. Also, the integration of energy exchanges (e.g. EEX) are foreseen within the optimising model. As the plant dispatch mainly influences the marginal costs, the important effects and coherences will be highlighted. As prices on the energy exchange have to be set as exogenous input, their influence on the marginal costs will also be discussed.

A major food safety issue in pork is Salmonella contamination. A stochastic state-transition simulation model was described to simulate the spread of Salmonella from multiplying through slaughter, with special emphasis for critical control points to prevent or reduce Salmonella contamination. Design of Experiments and metamodelling were used for a sensitivity analysis. The finishing stage and the slaughterhouse appeared to be the most important stages in the supply chain to reduce the prevalence of Salmonella contaminated carcasses.

Biological neural system can be considered as a series of biochemical reactions and signal transmission. It is important to provide an intuitive representation of the neural system to biologists while keeping its computational consistency. In this paper, we propose a method to exploit Hybrid Petri Net (HPN) for intuitive representation and quantitative modeling. The HPN is an extension of Petri Nets and represented by a directed, bipartite graph in which nodes are either discrete/continuous places (such as ion channels) or discrete/continuous transitions (such as phosphorylation), where places represent conditions and transitions represent activities. It can easily model the interactions among receptors, ionic flows (such as calcium), G-proteins, protein kinases and transcription factors that are very complicate in terms of the dynamics of all participants and their correlations. We demonstrate that, in the biological neural system, it is possible to translate and map these complex phenomena into HPNs in a natural manner. In our model, the dynamic properties of the neural signal processing can be examined, especially the interactions among neural modulators and signal transduction pathways. With such a mechanism model in hand, our ability to collaborate with neural scientists is greatly enhanced so as to simulate and examine the robustness of the neural transmission under the local biochemical perturbations.

This study concerns modeling, approximation and inference of gene regulatory dynamics on the basis of gene expression patterns. The dynamical behavior of gene expressions is represented by a system of ordinary differential equations. We introduce a gene-interaction matrix with some nonlinear entries, in particular, quadratic polynomials of the expression levels to keep the system solvable. The model parameters are determined by using optimization. Then, we provide the time-discrete approximation of our time-continuous model. Finally, from the considered models we derive gene regulatory networks, discuss their qualitative features and provide a basis for analyzing networks with nonlinear connections.

In this study the joint dynamics between stock prices and trading volume are investigated using data from the German stock market. Our results indicate no relations (contemporaneous as well as dynamic) between return levels and trading volume but strong linkages between return volatility and volume data. On including trading volume in the conditional volatility framework (GARCH-type) we provide empirical evidence for the importance of volume data as an indicator for the flow of information on the market. Applying Granger’s test for causality we detect also feedback relations between trading volume and return volatility. These findings corroborate our assumption that trading volume indirectly contains information about stock prices due to its relation to return volatility.

The generating function of the autocorrelations of successive waiting times in a stationary M/G/l or in a stationary GI/M/1 system can be expressed in terms of the probability generating function of the number of customers served in a busy period. The latter function is only implicitly determined as a solution to a functional equation. More explicit expressions have been obtained with the aid of Lagrange’s theorem on the reversion of power series, but they involve increasingly higher order derivatives of a function which comprises several Laplace-Stieltjes transforms. A recently discovered substitution method for contour integrals allows the numerical inversion of an implicitly determined generating function without the numerical solution of the functional equation for many complex values.

We consider multiobjective optimization problems in which objective functions are in the form of mathematical expectation of functions depending on a random element and a constraints set can depend on a probability measure. An efficient points set characterizes the multiobjective problems very often instead of the solution set in one objective case. A stability of the efficient points set (w.r.t. a probability measures space) and empirical estimates have been already investigated in the case when all objective functions were assumed to be strongly convex. The aim of the contribution is to present a modified assertions under rather weaker assumptions.

Consider the following situation of two-step shortlisting: two experts Alice and Bob are faced with a large number of alternatives which they can only observe imprecisely. They have to choose one of the alternatives, without knowing which one is best. Alice first compiles a shortlist of alternatives by choosing her

k

best observations. Bob then chooses his best observation among the shortlisted alternatives. Previous research showed that this procedure sometimes yielded worse results than if a single expert made the entire decision himself. Here, we consider an urn containing

n

— 1 homogeneous balls and one ball with larger weight. When drawing balls at random from the urn, the probability of drawing any one ball is proportional to its weight. Alice draws

k

balls and puts them in another urn, from which Bob then draws a single ball. Which value of

k

maximizes the probability that Bob draws the distinguished ball?

This note studies the variance of total cumulative rewards for Markov reward chains in both discrete and continuous time. It is shown that parallel results can be obtained for both cases.

First, explicit formulae are presented for the variance within finite time. Next, the infinite time horizon is considered. Most notably, it is concluded that the variance has a linear growth rate. Explicit expressions are provided, related to the standard average reward case, to compute this growth rate.

New conjugate directions algorithms are proposed, which are based on an orthogonalization procedure and do not perform line searches. The orthogonalization procedure prevents the conjugate vectors set from the degeneracy, eliminates high sensitivity to computation errors pertinent to methods of conjugate directions, and thus enable us to solve large-scale minimization problems without preconditioning. Numerical experiments have confirmed high efficiency of the algorithms for minimizing large-scale quadratic functions.

We investigate the robust shortest path problem using the robust linear optimization methodology as proposed by Ben-Tal and Nemirovski. We discuss two types of uncertainty, namely, box uncertainty and ellipsoidal uncertainty. In case of box uncertainty, the robust counterpart is simple. It is a shortest path problem with the original arc lengths replaced by their upper bounds. When dealing with ellipsoidal uncertainty, we obtain a conic quadratic optimization problem with binary variables. We present an example to show that a subpath of a robust shortest path is not necessarily a robust shortest path.

In the paper a problem of finding a maximum-weight spanning connected subgraph with given vertex degrees is considered. The problem is MAX SNP-hard, because it is a generalization of a well-known Traveling Salesman Problem. Approximation algorithms are constructed for deterministic and random instances. Performance bounds of these algorithms are presented.

The paper deals with a scheduling problem on the parallel processors, in which the sum of values of all the jobs is maximized. The value of job is characterized by a stepwise non-increasing function. Establishing an order of processing of datagrams which are sent by multiprocessor router is a practical example of application of this problem. It was already proved that its single processor case is NP-hard, thus the problem is also NP-hard. Therefore, two pseudo-polynomial time algorithms for the problem with common moments of job value change and a polynomial time algorithm for the case with identical processing times are constructed. It is also constructed and experimentally tested a number of heuristic algorithms which solve the general version of the problem.

We consider a new NP-hard optimization problem, the Prize Collecting Connected Subgraph Problem, which appears as a subproblem in routing of snow plows during snow fall. In this problem we have a set of edges in an undirected network, with edge costs and edge times. Moreover there is a time budget. The problem is to find a connected subset (corresponding to a snowplow tour) of minimal cost subject to the budget constraint. This problem can be modeled using flow constraints or introducing valid inequalities. We exemplify computations for the classical Sioux Falls Network

This paper presents a Less Flexibility First (LFF) based algorithm for solving container loading problems in which boxes of given sizes are to be packed into a single container. The objective is to maximize volume utilization. LFF, firstly introduced in [An effective quasi-human heuristic for solving the rectangle packing problem, European Journal of Operations Research 141 (2002) 341], is an effective deterministic heuristic applied to 2D packing problems and generated up to 99% packing densities. Its usage is now extended to the container loading problem. Objects are packed according to their flexibilities. Less flexible objects are packed to less flexible positions of the container. Pseudo-packing procedures enable improvements on volume utilization. Encouraging packing results with up to 93% volume utilization are obtained in experiments running on benchmark cases from other authors.

Nowadays, manufacturing industries — driven by fierce competition and rising customer requirements — are forced to produce a broader range of individual products of rising quality at the same (or preferably lower) cost. Meeting these demands implies an even more complex production process and thus also an appropriately increasing request to its scheduling. Aggravatingly, vagueness of scheduling parameters — such as times and conditions — are often inherent in the production process. In addition, the search for an optimal schedule normally leads to very difficult problems (NP-hard problems in the complexity theoretical sense), which cannot be solved efficiently.

With the intent to minimize these problems, the introduced heuristic method combines standard scheduling methods with fuzzy methods to get a nearly optimal schedule within an appropriate time considering vagueness adequately.

Data Envelopment Analysis (DEA) is designed to measure the efficiency of decision making units (DMUs). A scalarizing function reduces all numerical information on inputs and outputs of a DMU to a single efficiency score. A range adjusted measure normalizes input and output values through equalization factors, already known from Multicriteria Decision Making. Cooper et al (1999) introduce a range adjusted DEA model for a non-radial measure with variable returns to scale. We extend this approach by the help of a general DEA model framework. Calculation of suitable range adjusted measures is incorporated in a web-based DEA-tool. This tool allows processing of individual sets of data with a broad choice of model characteristics.

The theoretical concept of data envelopment analysis (DEA) was published by Charnes, Cooper and Rhodes in 1978. It is a powerful tool for assessing the efficiency of decision making units (DMUs) by comparing their respective inputfactors and output quantities. More precisely, the efficiency of a DMU is measured as the relation between the sum of weighted outputs and of weighted inputs, where the weights for a DMU are the solution of a linear optimization problem. But this approach suffers from a lack of objectivity due to the fact that every DMU wants an advantageous evaluation for itself, called self-appraisal in the respective literature. The purpose of this paper is to present an extension of the evaluation process in such a way that every DMU’s performance will be calculated in an objective and fair manner. For this a fuzzy oriented approach will be formulated which yields a nonlinear optimization problem. The resulting input/output weights are a compromise of all DMU’s individual interests. The so far developed theoretical concept will be applied to a company of Taiwanese semiconductor industry. Five DMUs’ efficiencies will be calculated over three years. Professional software solves the nonlinear program and the results permit meaningful economical interpretations.

Um aus Standortdaten, die in Form digitaler Karten aus geographischen Informationssystemen vorliegen, Prognosen über die vorkommenden Pflanzenarten abzuleiten, benötigt man ein Regelwerk zur Verknüpfung dieser Informationen. Solche Regelwerke fehlen bislang. In Form linguistischer Terme liegt zwar ein bewährtes, anerkanntes Informationssystem vor, das Zeigerwertsystem nach Heinz Ellenberg, um dieses Zeigerwertsystem aber nutzbar zu machen, muss es zunächst übersetzt werden. Das hier vorgestellte System stellt diese Übersetzung in Form eines Fuzzy-Expertensystems dar. Durch die Verknüpfung von Standortdaten und den Zeigerwerten nach Ellenberg über die Übersetzung der Zeigerwerte, kann so eine Verknüpfung von Standortdaten und den vorkommenden Pflanzen abgeleitet werden. Diese Verknüpfung erfolgt in Form eines Filters, der für jede untersuchte Pflanzenart die Auftrittschance auf dem Standort in Form einer Zugehörigkeitsbeschreibung bestimmt. Auf dieser Information lassen sich eine Vielzahl weiterer Ansätze aufbauen.

Support Vector Machines (SVM) from statistical learning are very powerful methods which can be used as (e.g.binary) classifiers or discriminators in a wide range of applications. Advantages of SVM are that weak prior assumptions about both model and data suffice. Moreover, optimization of the SVM essentially regularizes the emerging data model by restricting the model to special data points, the support vectors, usually a small subset from the training data. In our paper we discuss ways of detecting informative and typical subsets from SVM solutions, with the aim of extracting simple rules.

We present a model for the pressure between positions in a network. This notion is made operational through identifying the locations and sources of network value. Precisely these ‘markets’, where network value is obtained and generated, can be at stake and determine the pressure a position may experience. Using a limit approach, we also derive our square law of network power.

In this paper, we describe an extension of the OLAP (On-Line Analytical Processing) framework with automated causal diagnosis, offering the possibility to automatically generate explanations and diagnostics to support business decision tasks. This functionality can be provided by extending the conventional OLAP system with an explanation formalism, which mimics the work of business decision makers in diagnostic processes. The central goal of this paper is the identification of specific knowledge structures and reasoning methods required to construct computerized explanations from multidimensional data and business models. The methodology was tested on a case study involving the comparison of financial results of a firm’s business units.

Several business intelligence concepts show that it is possible to build a data warehouse based on heterogeneous quantitative and qualitative data. But the danger of flooding the management with information still remains. Business information should be made available according to the personal need of a manager by a self-defined push mechanism. The concept of active data warehousing is going to be expanded in this way, first. Messages about new relevant information should be created for quantitative and qualitative data as well. Due to this, there is a need for an enterprise specific ontology. This ontology works as an intermediate between current information and user profiles. Just interesting information are passed to the user. The second approach clusters qualitative data in favour of visualization. The usage of increasing cell structures provides a self organizing map. Decision makers will get the opportunity to search in document volumes, which are clustered.

Im Rahmen der High-Tech-Offensive Bayern (HTO) wurde an der Fachhochschule Augsburg für die Virtuelle Hochschule Bayern (VHB) eine Web-basierte „Selbstleraumgebung Operations Research (OR)“ entwickelt. Ziel war es, vornehmlich Studierenden der Fachrichtungen Wirtschaftsinformatik und Informatik, eine OR-Vorlesung virtuell bzw. online anzubieten, mit der sie sich die grundlegenden OR-Verfahren im Selbststudium aneignen können.

Das unter diesen Voraussetzungen entwickelte Lernprogramm wird seit gut einem Jahr intensiv von Studierenden verschiedener Hochschulen genutzt. Wesentliche Besonderheit dieses Lernprogramms ist der explorative Charakter:

Neben dem eigentlichen Lehrbuch, das im Wesentlichen aus einem Online-Skriptum besteht, gibt es eine Sammlung von über 60 Java-Applets. Diese simulieren die theoretisch vorgestellten Algorithmen anhand von frei wählbaren Werten, indem sie jeden Schritt erklären. In diesen Simulationen kann der Lernende schrittweise die Algorithmen an eigenen Beispielen selbst „entdecken“.

Das umgesetzte Konzept ermöglicht den Studenten auch einen iterativen Lernprozess und die Möglichkeit einer effizienten Wissensauffrischung. Die bisherigen Erfahrungen mit dem Lernprogramm und die durchgeführten Studentenevaluationen werden vorgestellt und grob analysiert.

Die Selbstlernumgebung im Gesamten entspricht den Vorstellungen der deutschen HRK (Hochschulrektorenkonferenz), die in Selbstlernumgebungen Lehrangebote sieht, die eigenständig und selbstbestimmend und praktisch ohne Betreuung von den Lernenden bearbeitet werden und die damit auf die Lehrbedürfnisse, Lerngeschwindigkeiten und das individuelle Zeitbudget Rücksicht nehmen.

Eine weitere Besonderheit ist die einfache Erweiterbarkeit dieses Web-basierten Lernprogramms. Die flache Struktur erlaubt es weitere Texte und Applets zu integrieren. Um eine einfache Erstellung von interaktiven Übungen zu ermöglichen, wurde ein Autorenwerkzeug entwickelt, das es ermöglicht, ohne jegliche Java Kenntnisse, Java-Übungs-Applets mit automatischer Auswertung zu erstellen. Zum Abschluss des Vortrags wird dieses Werkzeug, das mittlerweile auch in anderen E-Learning-Projekten eingesetzt wird, in seinen elementaren Funktionen vorgestellt.

Crew scheduling for airlines requires an optimally scheduled coverage of flights with regard to given timetables. We consider the crew scheduling and rostering process for airlines, where crew members are stationed unevenly among home bases. In addition, their availability changes dynamically during the planning period due to pre-scheduled activities, such as office and simulator duties, vacancy, or requested off-duty days.

Besides this highly complex setting, crew satisfaction becomes more and more important: Recent approaches focus on a variety of quality-of-life criteria like the consideration of individual preferences. Hence most of them are applied to individual rosters; certain aspects especially for the appropriate handling of teams are neglected. Therefore the introduced concept of Team-oriented Rostering addresses the upcoming demand for a reduction of the usually high amount of team changes among crew members within daily or day-by-day team compositions. It relies on the optimal set of roster combinations for the scheduled crew members within the assignment step.

The combination of process integration and Operations Research enables an integrated technique assessment and a subsequent process design. The application of Multi Objective Pinch Analysis (MOPA) permits the identification of overall saving potentials for energy, water and Volatile Organic Compounds (VOC). In this paper the general concept of MOPA is described and its application is shown in its first steps for a bicycle coating plant in Chile.

Manufacturing companies in a make-to-order environment sell customer specific products. Usually, a company offers more than one product, faces a stochastic demand, and a time-varying product price. The latter cannot entirely be set autonomously by the company due to competitors. The decision the company has to make for an incoming order is whether to accept or reject the order, depending on the remaining capacity, the contribution margin of the order and the orders expected for the future. In our contribution we will discuss if the methods for the airline revenue management are applicable to the described problem. After giving an overview about the requirements a decision support system ought to fulfill to improve the order selection process in a make-to-order environment, we will discuss the differences of such a system to existing revenue management approaches in service industries. Subsequently, we give a mathematical formulation for the described problem and apply it to a simplified practical example.

In this paper the approach of combining predictions is used to benefit from the advantages of forecasts predicting on different levels, to reduce the risks of high noise terms on low level predictions and overgeneralization on higher levels. The presented experimentally compared approaches of combining seasonal airline demand forecasts differ concerning input decomposition, multilevel structures, combination models and kinds of aggregation. Significant forecast improvements have been obtained when using multilevel, hierarchical structures.