Abstracts presentations phd students
BIJVANK, MARCO
Department of Mathematics
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
mbijvank@few.vu.nl
Supervisor
Koole
Heuristics for Car Stock Management
Abstract
In this presentation we focus on the repair kit problem, which is a special case of a multi-item inventory system. High customer service is becoming an important strategy to increase the competitiveness of a firm. Since customers perceive a good quality of service when all the items they demand are on stock, it becomes more realistic to model customer satisfaction with an order-based service level. A well known problem from literature is the repair kit problem, which has an after sales service setting. In this problem technicians visit customers to repair machine failures and extra costs are incurred whenever the repairer has to come back to complete a repair if not all the required parts were available at the first visit. Therefore, technicians have to take along some spare parts, taking into account the holding costs (and other limitations like space or budget). Most (practical) models implement a cost minimization objective, while a service requirement is neglected. We have improved the most general heuristic for cost minimization models as well as for service agreement models, such that we achieve near-optimal solutions which indicate which spares to take and in which quantity.
| Back to home page | Program | Parallel sessions |
CORBACIOGLU, UMUT
Rotterdam School of Management
Erasmus University
P.O. Box 1738
3000 DR Rotterdam
ucorbacioglu@rsm.nl
Supervisor
Van der Laan
Title
Setting the holding cost rates in a multi-product system with
remanufacturing
The Net Present Value (NPV) approach is considered to be the right approach to study inventory systems since it accounts for the cash flows as is. The average cost (AC) approach is more widely used in both practice and theory. However, the opportunity cost interpretation of AC framework is not that straightforward in systems with joint manufacturing and remanufacturing.
In such systems, in the end-product (serviceable) stock, manufactured and remanufactured items are present. Due to this convergent structure, the valuation of serviceable inventory is ambiguous. Also, in the analysis another stock point for returned items (remanufacturables) is considered. Returned products are acquired for less investment, but they have a potential of being added to serviceable inventory with less expenditure than manufacturing. Moreover, remanufacturing can be used to convert returns into different products. This divergent structure which is a natural result of designs that allow disassembly and reuse adds another layer of ambiguity on opportunity cost interpretation.
In this paper we analyse a two-product system with manufacturing and remanufacturing operations in a deterministic setting. For this system, by considering two different models under a net present value (NPV) approach and an average cost (AC) approach, we determine holding cost rates such that the two approaches are approximately equivalent. Then we demonstrate the effect of traditional valuation methodology on the remanufacturing operation dynamics by comparing that approach to the theoretical results of our analysis.
| Back to home page | Program | Parallel sessions |
DIEPEN, GUIDO
Institute of Information & Computing Sciences
University of Utrecht
Padualaan 14
3584 CH Utrecht
diepen@cs.uu.nl
Supervisors
Van den Akker/Hoogeveen
Title
Minimizing total weighted tardiness on a single machine with release
dates and equal-length jobs
In this paper we look at the problem where we have to schedule n jobs with release dates, due dates, weights, and equal processing times on a single machine. The objective is to minimize the sum of weighted tardiness (1 | rj, pj = p | ∑wjTj in the three-field notation scheme). We formulate the problem as a time indexed ILP after which we solve the LP-relaxation. We show that for certain special cases (namely when either all due dates, all weights, or all release dates are equal, or when all due dates and release dates are equally ordered), the solution for the LP-relaxation is either integral or can be rewritten in polynomial time into an integral one. For the general case we present a branching rule that performs well. Furthermore we show that the same approach holds for the m parallel machines variant of the problem. Finally we show that with a minor modification the same approach also holds for the single-machine problems of minimizing the sum of weighted late jobs (1 | rj, pj = p | ∑wjUj) and the sum of weighted late work (1 | rj, pj = p | ∑wjVj) as well as their respective m parallel machines variants.
| Back to home page | Program | Parallel sessions |
DOBBER, MENNO
Department of Mathematics
Vrije Universiteit Amsterdam
De Boelelaan 1081a
1081 HV Amsterdam
amdobber@few.vu.nl
Supervisor
Koole
An Effective Prediction Method for Running Times of Jobs on Shared Processors
Abstract
Grid computing is an emerging technology by which huge numbers of processors over the world create a global source of processing power. Their collaboration makes it possible to perform computations that are too extensive to perform on a single processor. On a grid processors may connect and disconnect at any time, and the load on the computers can be highly bursty. Those characteristics raise the need for the development of techniques that make grid applications robust against the dynamics of the grid environment. In particular, applications that use significant amounts of processor power for running jobs need effective predictions of the expected computation times of those jobs on remote hosts. Currently, there are no e_ective prediction methods available that cope with the ever-changing running times of jobs on a grid environment. Motivated by this, we develop the Dynamic Exponential Smoothing (DES) method to predict running times in a grid environment. We have performed extensive experiments in a real global-scale grid enviroment to compare the e_ectiveness of DES. The results demonstrate that DES strongly and consistently outperforms existing prediction methods.
| Back to home page | Program | Parallel sessions |
EGOROVA, REGINA
CWI
Kruislaan 413
1090 GB Amsterdam
r.egorova@cwi.nl
Supervisors
Borst, Boxma and Zwart
Sojourn Time Tails in the M/D/1 Processor Sharing Queue
Abstract
We consider the sojourn time V in the M/D/1 processor sharing (PS) queue, and show that P(V > x) is of the form Ce -γx as x becomes large. The proof involves a geometric random sum representation of V, and a connection with Yule processes, which also enables us to simplify Ott's (1984) derivation of the Laplace transform of V. Numerical experiments show that the approximation P(V > x) ≈ Ce-γx is excellent even for moderate values of x. In addition, we present some results on tail behavior of the conditional sojourn time in PS queue with exponential service.
| Back to home page | Program | Parallel sessions |
ELABWABI, GAMAL
Delft University of Technology
Mekelweg 4
2628 CD Delft
g.elabwabi@ewi.tudelft.nl
Supervisor
de Klerk
Nonnegative bilinear functions on the cartesian product of Lorentz cones
Abstract
We will study the cone of nonnegative bilinear functions on the
cartesian product of Lorentz cones and it's dual. We will derive LMI
characterizations of this cone and its dual. We prove that it is
possible to optimize over this cone and it's dual using Semidefinite
programming in polynomial time. We will also present some applications
of our result in optimization as well as in general linear algebra.
| Back to home page | Program | Parallel sessions |
GVOZDENOVIC, NEBOJSA
CWI
Kruislaan 413
1090 GB Amsterdam
nebojsa@cwi.nl
Supervisor
Laurent
Approximating the Chromatic Number of a Graph by Semidefinite Programming
Abstract
The Lovász theta number of a graph is a well studied graph parameter that can be computed efficiently to an arbitrary precision in polynomial time by using semidefinite programming. It is known to be "sandwiched" between two "NP-hard" parameters, i.e. the stability number of a graph and the chromatic number of a graph complement. Recently, several hierarchies of semidefinite bounds, starting either from the Lovász theta or one of its strengthenings were proposed in order to approximate the stability number of a graph. It turned out that some bounds in these hierarchies that can be computed efficiently give better approximations for the stability number than the Lovász theta number for certain graph classes. We show how these hierarchies can be adapted for approximating the fractional chromatic number, and the chromatic number of a graph. We prove that our new bounds are at least as good as the best known semidefinite lower bounds on the chromatic number of a graph. In addition, we give some computational results that show that in some cases our bounds are better.
| Back to home page | Program | Parallel sessions |
HAIJEMA, RENÉ
Department of Quantitative Economics
University of Amsterdam
Roetersstraat 11
1018WB Amsterdam
r.haijema@uva.nl
Supervisor
Van der Wal
Blood Platelet Production: Optimization by Dynamic Programming and Simulation
Abstract
Blood banks produce and store blood products in order to fulfill 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. The demand may be categorized into two groups: demand for ‘young’ platelet pools (at most three days old) and demand that can be met by pools of any age up to the maximal lifetime. Production volumes need to be chosen carefully in order to reduce outdating while keeping the occurrence of shortages low. In current (national and foreign) practice about 15 to 20% of pools are not used because of outdating. We show that by applying a simple rule outdating can be reduced to less than 1%.
We investigate the structure of the optimal production policy by solving a down sized periodic Markov Decision Problem (MDP). Down sizing is required to overcome the curse of dimensionality in the state space. An innovative frequency table, obtained via simulation, depicts the structure of the optimal MDP strategy. The optimal production volumes appear to depend on the number of pools on stock and their ages. A simple rule can be derived, with two parameters for each working day. By a simulation based search algorithm we find optimal values for the parameters in realistic sized cases.
Via an extensive simulation study (for one of the four Dutch blood banks) we show that the simple rule performs quite well (nearly optimal) even if one acknowledges:
- the distinction of multiple and limited compatible blood groups;
- the uncertainty in the supply by donors;
- that 70% of the demand prefers ‘young’ platelets.
| Back to home page | Program | Parallel sessions |
HEUVEL, WILCO VAN DEN
Econometric Institute
Erasmus University
P.O. Box 1738
3000 DR Rotterdam
wvandenheuvel@few.eur.nl
Supervisor
Wagelmans
Title
Lower bounds on the worst case ratio for a class of heuristics for
the economic lot-sizing problem
The economic lot-sizing problem is described as follows. Given the (deterministic) demand for a discrete and finite planning horizon, find the production schedule that satisfies the demand and minimizes the total costs. Costs include setup cost for each time period production takes place and holding cost for each item carried over from a period to the next period.
Although the problem can be solved to optimality in polynomial time, heuristics are often applied when the problem has to be solved in a rolling horizon environment. A certain class of heuristics possesses the so-called insulation property, i.e., previous set production periods cannot alter while constructing the overall production schedule. In other words, given the production quantities scheduled up to period t, only the production quantity in the last production period may change when considering period t+1.
It is shown in the literature that there exist heuristics satisfying the insulation property that have a worst case ratio of 2. In this talk we try to find bounds on the worst case ratio for all heuristics satisfying the insulation property. We consider the problem as a kind of online scheduling problem and derive a methodology to find lower bounds on the worst case ratio for a fixed number of periods T. The first results show that for large T we can find lower bounds close to 1.5. That means, for each heuristic satisfying the insulation property, there exist problem instances for which the heuristic constructs solutions with a worst case ratio close to 1.5.
| Back to home page | Program | Parallel sessions |
HEYDENREICH, BIRGIT
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
b.heydenreich@ke.unimaas.nl
Supervisors
Uetz/Müller
Mechanisms for Decentralized Online Scheduling
Abstract
We study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time - P | rj | ∑ wjcj in the notation of Graham et al. [1] - from a new perspective: We assume a strategic setting, where the data of each job, namely its release date rj, its processing time pj and its weight wj is only known to the job itself, but not to the system. Furthermore, we assume a restricted communication paradigm, referred to as decentralizationP = NP. In addition, in the strategic setting, selfish agents trying to maximize their own benefit can do so by reporting strategically about their private information, thus manipulating the resulting outcome.
We present a polynomial time mechanism for this setting building upon the MinIncrease-algorithm from [3]. As usual in mechanism design, the mechanism defines payments that have to be made by the jobs for being processed. We show that there does not exist a payment scheme that extends the MinIncrease-algorithm to a mechanism in a way that makes truthful revealing of private information an ex-post dominant strategy for every job. The payments we introduce make truthful reporting of private information a dominant strategy at least for myopic rational jobs. Those payments result in a balanced budget and can be computed online. We show that those payments enable us to decentralize the mechanism according to the restricted communication paradigm. The resulting mechanism is 3.281-competitive which coincides with the bound that is known for the non-strategic setting. An earlier version of the paper is available as a Meteor Research Memorandum [2].
References
[1] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5: 287-326, 1979.
[2] B. Heydenreich, R. MMüller and M. Uetz. Mechanisms for Decentralized Online Scheduling, Meteor Research Memorandum, Maastricht University, 2005.
[3] N. Megow, M. Uetz and T. Vredeveld. Stochastic Online Scheduling on Parallel Machines. In G. Persiano and R. Solis-Oba, editors, Proc. Second International Workshop on Approximation and Online Algorithms, volume 3351 of Lecture Notes in Computer Science, pages 167-180. 2005.
| Back to home page | Program | Parallel sessions |
LIESHOUT, PASCAL
CWI
Kruislaan 413
1098 SJ Amsterdam
p.m.d.lieshout@cwi.nl
Supervisor
Mandjes
Title
Tandem Brownian Queues
Abstract
We analyze a two-node tandem queue with Brownian input. We first derive
an explicit expression for the joint distribution function of the
workloads of the first and second queue, which also allows us to
calculate their exact large-buffer asymptotics. The nature of these
asymptotics depends on the model parameters, i.e., there are different
regimes. By using sample-path large-deviations (Schilder's theorem)
these regimes can be interpreted: we explicitly characterize the most
likely way the buffers fill. These results are derived by first
considering the closely related two-node parallel queue, for which
similar results are obtained.
| Back to home page | Program | Parallel sessions |
LOON, JOYCE VAN
Department of Quantitative Economics
Maastricht University
P.O. Box 616
6200 MD Maastricht
j.vanloon@ke.unimaas.nl
Supervisors
Van Hoesel/Uetz
How to Sell a Graph: Some Guidelines for the Graph Retailer
Abstract
We consider a profit maximization problem when pricing a set of m items which can be represented as the edges of an undirected graph G. There is a set of n customers, each of which is interested in purchasing a path in the graph. The path is also called a customer's bundle, and each customer has a known budget for her respective bundle. Customers are single minded, so they are only interested in that particular bundle. The objective is to find a pricing and a feasible assignment of items to customers in order to maximize total profit. We give an overview of recent results on the tractability of that class of profit maximization problems. While recent papers mainly address the case of unlimited availability of the items [1,3,5,6], we particularly focus on the problem with limited availability of items. Our results are as follows. When the graph G is a path, we derive a fully polynomial time approximation scheme, complementing previous approximation schemes, and matching a recent NP-hardness proof [2,3]. If the graph G is a tree, and all items are unique, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the graph G is a grid, and items are unique, we show that it is even NP-complete to approximate the problem within n1-ε.
This talk is based on joint work with Alexander Grigoriev, Marc Uetz and René Sitters [4].
Keywords: Pricing problems, tollbooth problem, computational complexity, dynamic programming, fully polynomial time approximation scheme.
References
[1] M.F. Balcan and A. Blum, Approximation algorithms for item pricing, Working paper, 2005.
[2] H. Bodlaender and E. Penninkx, An elegant NP-completeness proof for profit maximization on paths, May 2005.
[3] P. Briest and P. Krysta, Single-minded unlimited supply pricing on sparse instances, Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, 2006, to appear.
[4] A. Grigoriev, J. van Loon, R. Sitters, and M. Uetz, How to sell a graph: Some guidelines for the graph retailer, Working paper, 2005.
[5] V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry, On pro¯t-maximizing envy-free pricing, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, 2005, pp. 1164-1173.
[6] J. D. Hartline and V. Koltun, Near-optimal pricing in near-linear time, Algorithms and Data Structures (F. K. H. A. Dehne, A. López-Ortiz, and J.-R. Sack, eds.), vol. 3608, Springer, 2005, pp. 422-431.
| Back to home page | Program | Parallel sessions |
MANSOURI, HOSSEIN
Delft University of Technology
Mekelweg 4
2628 CD Delft
h.mansouri@ewi.tudelft.nl
Supervisor
Roos
A simplified O(nL) infeasible interior-point algorithm for linear optimization using full Newton steps
Abstract
Interior-Point Methods (IPMs) for solving linear optimization
problems have polynomial complexity and also are highly efficient
in practice. An interesting fact is that almost all known
polynomial time variants of IPMs use the so called central path as
a guideline to the optimal set, and some variant of Newton's
method is used to follow the central path approximately. There
exists two kind of interior-point methods the feasible IPMs and
the infeasible IPMs (IIPMs). Feasible IPMs start with a strictly
feasible interior point and maintain feasibility during the
solution process. Infeasible IPMs start with an arbitrary positive
point and feasibility is reached as optimality is approached. The
best know iteration bound for IIPMs is O(n log(n/ε)), where n
denotes the dimension of the problem. Recently C. Roos presented the
first primal-dual infeasible interior-point
algorithm that uses full-Newton steps for solving the linear
optimization problem and proved that its iteration bound coincides
with the best known bound for infeasible interior-point
algorithms. Each iteration consists of a step that restores the
feasibility for an intermediate problem (the so-called feasibility
step) and some usual centering steps. No more than
n iterations (where n is number of inequalities) suffice
to reduce the duality gap and the residuals by the factor
1/ε. In this paper we use a different feasibility step and show
that with a simpler analysis the same result can be obtained.
| Back to home page | Program | Parallel sessions |
MES, MARTIJN
Department of Operational Methods for Production and
Logistics
University of Twente
P.O.Box 217
7500 AE Enschede
m.r.k.mes@utwente.nl
Supervisor
Van Harten
Title
Opportunity costs calculation in agent-based vehicle routing and
scheduling
In this talk we consider a real-time, dynamic pickup and delivery problem with time-windows where orders should be assigned to one of a set of competing transportation companies. This assignment is made in a sequential second-price auction marketplace. Our approach decomposes the problem into a multi-agent structure where vehicle agents are responsible for the pricing, routing and scheduling decisions. Therefore the system performance will be heavily dependent on the pricing strategy of the vehicle agents. We propose a pricing strategy which not only takes the direct cost of a job insertion into account, but also the so-called opportunity costs. These opportunity costs are used to capture the loss in expected future revenue of a vehicle schedule due the insertion of a new job. In order to calculate expected future revenue we have to look at all possible future scenario's that can take place given a certain schedule. These possible scenarios are described by a Markov Decision Process (MDP). Simulation is used to evaluate the benefit of pricing opportunities compared to simple pricing strategies in different market settings. Numerical results show that the proposed approach provides high quality solutions, in terms of profits, capacity utilization and delivery reliability. We explained these results from the following behavior of the vehicle agents. First, they tend to schedule unattractive jobs later increasing the probability of combining this job with another job. Second, they tend to create gaps before unattractive jobs, possibly reducing empty moves. Third, they tend to pick out only the most profitable jobs.
| Back to home page | Program | Parallel sessions |
MINCSOVICS, GERGELY
Eindhoven University of Technology
P.O. Box 513
5600 MD Eindhoven
g.z.mincsovics@tm.tue.nl
Supervisor
Bertrand/Dellaert
Title
Workload-dependent capacity control
The development of job intermediation and the increasing use of Internet allow companies to carry out quicker and quicker capacity changes. In many cases capacity adaptation can be driven according to the present workload. We introduce a set of Markov chain models to represent workload-dependent capacity control policies. In our analysis we assume exponential interarrival and service times, although the model permits extension to phase-type distributions. We present two analytical approaches to stationary analysis in order to evaluate the policies due-date performance. One provides an explicit expression of throughput time distribution, the other is a smart vector iteration method that calculates the moments of the throughput time. Eventually, we compare due-date performances, capacity costs, costs of changing capacity, lost sales and select optimal policies. Our results and tools can be used by manufacturing and service industries when declaring a static policy for a dynamic, workload-dependent capacity planning.
| Back to home page | Program | Parallel sessions |
TENNEKES, MARTIJN
Department of Mathematics
Maastricht University
P.O. Box 616
6200 MD Maastricht
martijn.tennekes@math.unimaas.nl
Supervisor
Vrieze
Variations on network formation games
Abstract
Network structures play an important role in many fields, e.g. in sociology and economics. Individuals are able to share information via the links of these networks. In line with Jackson and Wolinksy [2] and Bala and Goyal [1] (among others) we focus on the formation of these networks. We model the network formation as a non-cooperative game, which is a generalization of a game described by Bala and Goyal [1]. Consider a set of players where each player has some information value on his own. Furthermore, a player has access to another player's information value if they are connected, directly or indirectly. The underlying graph is directed. The links have certain costs. In a move, a player chooses with whom he contruct links. Players move sequentially in random order.
The pay-off of a player is defined by the total information value that he gains minus the total costs of the links he constructs. Our goal is to find the Nash equilibria of this game. Furthermore, we want to know if these equilibria can be reached through a succession of moves and what the corresponding convergence rates are. Our first result is that we have found examples for which no Nash equilibria exist.
References
[1] V. Bala and S. Goyal, A non-cooperative model of network formation, Econometrica 68 (2000) 1181-1229.
[2] M. O. Jackson and A. Wolinsky, A Strategic Model of Social and Economic Networks, Journal of Economic Theory 71 (1996) 44-74.
| Back to home page | Program | Parallel sessions |
VERHEIJEN, BAS
Rotterdam School of Management
Erasmus University
P.O. Box 1738
3000 DR Rotterdam
bverheijen@rsm.nl
Supervisors
Kuik and Van Nunen
Title
Transport Costs with Consolidation Effects
This presentation deals with transportation costs for products which that are sharing a capacitated transport resource , such as a trucks (LTL transport) on a single link. The aim is to understand and explain transport costs as a function of order quantity. Although actual transportation tariffs in the market have been described and studied before, few studies explain the functional form of transport costs and its dependencies on the environment. A thorough understanding of the costs for transport enables better judgement on potential benefits and use of third party logistics providers and gives insight in cost savings that could potentially be achieved when advanced supplier vendor arrangements such as Vendor Managed Inventories or Factory Gate Pricing are used. Requests for transport services arrive as orders. The time between order arrivals is stochastic and the size of each order is a stochastic discrete value. At certain constant intervals, all orders that have accumulated are dispatched to the customer. The orders are packed into trucks in an efficient manner and transported, in such a way that the least number of trucks are used and that orders are not split unnecessarily. We assume that ultimately, the cost per truck that is used is constant. These costs consist of a.o. fuel, wear and tear and wages. As observed in practice, transport costs depend on the order-quantities. The transport costs for individual orders are derived by allocating the total costs of transport for a dispatch to individual orders. Three different allocation methods are studied: the Shapley value, a semi-proportional allocation and calculation of the expected additional costs. The arrival, accumulation and dispatch of orders is simulated using a discrete event simulation model. The transport costs are subsequently determined according to the allocation methods. The intensity of order arrivals and the order-size distribution are varied in the simulation experiments. The resulting transport cost curves are strictly increasing in order-size. However, contrary to literature on transport tariffs, the curves are not concave.
| Back to home page | Program | Parallel sessions |
VIEIRA, MANUEL
Delft University of Technology
Mekelweg 4
2628 CD Delft
m.vieira@ewi.tudelft.nl
Supervisor
Roos
Interior Point Methods for symmetric optimization based on kernel functions
Abstract
Three symmetric cones are widely used in optimization, namely the
non-negative orthant, the cone of positive semi-definite matrices and
the second order cone. Several authors (Faybusovich, Alizadeh and
Schmieta) claim that is more profitable to direct their attention to
the more general problem of optimization over symmetric cones.
Roos, Bai and Elghami introduced and analyzed new search directions for
Interior point methods for linear optimization. The new search
directions are defined by univariate so-called kernel functions. Our
goal is to extend this work to general symmetric cones in a unified and
unique way.
Following these ideas we decided to generalize this recently developed
interior point methods based on kernel functions (as barrier function)
for linear optimization to the so-called symmetric optimization, in
which the theory of Jordan algebras give us the necessary tools for
this development.
| Back to home page | Program | Parallel sessions |
VLASIOU, MARIA
EURANDOM
Eindhoven of Technology
P.O. Box 513
5600 MB Eindhoven
vlasiou@eurandom.tue.nl
Supervisor
Adan
Exact solution to a Lindley-type equation on a bounded support
Abstract
In this talk, we are concerned with a Lindley-type equation arising
from alternating service models and carousel systems. In particular, we
derive the limiting distribution of W = max{0, B-A-W}, where we assume
that A is exponentially distributed and B has a polynomial
distribution. We apply the exact solution for this model in order to
derive approximations of the waiting-time distribution when B is
generally distributed on a finite support. Furthermore, we provide
error bounds for these approximations, and we show some numerical
results.
| Back to home page | Program | Parallel sessions |
WEIJ, WEMKE VAN DER
CWI
Kruislaan 413
1090 GB Amsterdam
weij@cwi.nl
Supervisor
Van der Mei
Stability and Throughput in a Two-Node Queueing Network with a Shared Resource
Abstract
We study stability and throughput in a two-layered queueing network consisting of two multi-server nodes, where at any time the busy servers share a common underlying resource in a processor-sharing fashion. We consider a two-node network with general stationary arrival processes, general service-time distributions at both queues, arbitrary numbers of servers at both queues, and multiple customer classes, each with a class-specific arrival rate and visit order. For this model we derive a full characterization of the per-queue stability and the per-class throughput, in a general parameter setting. The results reveal that the per-queue stability strongly and throughput depend on the βi/ci ratios of both queues, where βi is the mean service time and ci is the number of servers at queue i. Moreover, we obtain several interesting and seemingly counter-intuitive results, and provide explanations for these observations. As such the results provide new intuition and fundamental insights into the behavior of queueing networks with this multi-layered structure.
| Back to home page | Program | Parallel sessions |