A DFO technique to calibrate queueing models

A crucial step in the modeling of a system is to determine the values of the parameters to use in the model. In this paper we assume that we have a set of measurements collected from an operational system, and that an appropriate model of the system (e.g., based on queueing theory) has been developed. Not infrequently proper values for certain parameters of this model may be difficult to estimate from available data (because the corresponding parameters have unclear physical meaning or because they cannot be directly obtained from available measurements, etc.). Hence, we need a technique to determine the missing parameter values, i.e., to calibrate the model.As an alternative to unscalable “brute force” technique, we propose to view model calibration as a non-linear optimization problem with constraints. The resulting method is conceptually simple and easy to implement. Our contribution is twofold. First, we propose improved definitions of the “objective function” to quantify the “distance” between performance indices produced by the model and the values obtained from measurements. Second, we develop a customized derivative-free optimization (DFO) technique whose original feature is the ability to allow temporary constraint violations. This technique allows us to solve this optimization problem accurately, thereby providing the “right” parameter values. We illustrate our method using two simple real-life case studies.     

A unified view of product-form approximation techniques for general closed queueing networks

Two major approximate techniques have been proposed for the analysis of general closed queueing networks, namely the aggregation method and Marie's method. The idea of the aggregation technique is to replace a subsystem (a subnetwork) by a flow equivalent single-server with load-dependent service rates. The parameters of the equivalent server are obtained by analyzing the subsystem in isolation as a closed system with different populations. The idea of Marie's method is also to replace a subsystem by an equivalent exponential service station with load-dependent service rates. However, in this case, the parameters of the equivalent server are obtained by analyzing the subsystem in isolation under a load-dependent Poisson arrival process. Moreover, in Marie's case, the procedure is iterative.

In this paper we provide a general and unified view of these two methods. The contributions of this paper are the following. We first show that their common principle is to partition the network into a set of subsystems and then to define an equivalent product-form network. To each subsystem is associated a load-dependent exponential station in the equivalent network. We define a set of rules in order to partition any general closed network with various features such as general service time distributions, pupulation constraints, finite buffers, state-dependent routing. We then show that the aggregation method and Marie's method are two ways of obtaining the parameters of the equivalent network associated with a given partition. Finally, we provide a discussion pertaining to the comparison of the two methods with respect to their accuracy and computational complexity.     

A multi-class approximation technique for the analysis of kanban-like control systems

Analytical methods have been proposed in the literature for performance evaluation of kanban control systems. Among them, the method presented by Di Mascolo and colleagues appears to be of special interest since it can handle manufacturing stages consisting of any number of machines and it is fairly accurate. This paper presents a new way of deriving the analytical method presented by Di Mascolo et al. The approach is to see the queueing network of the kanban control system as a multiclass queueing network in which each kanban loop is represented by a class of customers. This allows one to use the general technique proposed in Baynat and Dallery for analysing multiclass queueing network using product-form approximation methods. In terms of equations, the new method is equivalent to that previously presented. However, the computational algorithm is much more efficient since it avoids the two levels of iterations involved in the original algorithm. Another major advantage of the new method over that originally proposed is that it provides a general framework for the analysis of more general kanban systems. Indeed, it is shown in this paper how this approach can easily be extended in order to handle kanban systems with multiple consumers and multiple suppliers, kanban-controlled assembly systems and generalized kanban systems.     

Improving retouched Bloom filter for trading off selected false positives against false negatives

Where distributed agents must share voluminous set membership information, Bloom filters provide a compact, though lossy, way for them to do so. Numerous recent networking papers have examined the trade-offs between the bandwidth consumed by the transmission of Bloom filters, and the error rate, which takes the form of false positives. This paper is about the retouched Bloom filter (RBF). An RBF is an extension that makes the Bloom filter more flexible by permitting the removal of false positives, at the expense of introducing false negatives, and that allows a controlled trade-off between the two. We analytically show that creating RBFs through a random process decreases the false positive rate in the same proportion as the false negative rate that is generated. We further provide some simple heuristics that decrease the false positive rate more than the corresponding increase in the false negative rate, when creating RBFs. These heuristics are more effective than the ones we have presented in prior work. We further demonstrate the advantages of an RBF over a Bloom filter in a distributed network topology measurement application. We finally discuss several networking applications that could benefit from RBFs instead of standard Bloom filters.     

Determining inventory levels in a CONWIP controlled job shop

We extend the concept of CONWIP control to a job shop setting, in which multiple products with distinct routings compete for the same set of resources. The problem is to determine the fixed overall WIP level and its allocation to product types (WIP mix) to meet a uniformly high customer service requirement for each product type. We formulate an optimization problem for an open queuing network model in which customer orders pull completed products from the system. Then, assuming heavy demand, we derive a throughput target for each product type in a closed queuing network and provide a simple heuristic to find a minimum total WJP and WIP mix that will achieve an operating throughput close to this target. In numerical examples, the WIP mix suggested by this approach achieves the customer service requirement with a relatively low total WIP     

Production Capacity of Flexible Manufacturing Systems with Fixed Production Ratios

Determining the production capacity of flexible manufacturing systems is a very important issue in the design of such systems. We propose an approach for determining the production capacity (i.e., the maximum production rate) of a flexible manufacturing system with several part types, dedicated pallets, and fixed production ratios among the different part types. We show that the problem reduces to the determination of a single parameter for which we propose an iterative procedure. Simulation or approximate analytical techniques can be used as the building block performance evaluation technique in the iterative procedure.     

Multiproduct Kanban-like Control Systems

Kanban Control Systems are widely used to control the release of parts in multistage manufacturing systems operating under a pull mechanism, i.e. production of new parts is triggered based on the actual demands arriving to the output of the system. Most of the work on Kanban Control Systems deals with single-product manufacturing systems, although Kanban Control Systems have also been used in multiproduct environments. The aim is to study in detail the behaviour of Kanban Control Systems in the context of multiproduct manufacturing systems. In addition to the classical Kanban Control System, we also consider two more general Kanban-Like Control Systems known as Generalized Kanban Control System and Extended Kanban Control System. When extending these pull control mechanisms to multi-product systems, we distinguish two cases, whether kanbans are dedicated to a single part type or shared among the different part types. We provide an in-depth analysis of each of the resulting control mechanism and discuss some important issues arising from the study.     

Improving the MAC Layer of Multi-Hop Networks

Ad hoc and multi-hop networks will probably be a part of the fourth generation of wireless networks, which will integrate networks of several sizes and capacities with heterogeneous coverage: cellular networks (3G), WLAN hot spots, wireless personal area networks (WPAN) and wireless body area networks (WBAN). In this context, MAC protocols play a deciding role for a high utilization of the wireless channel. In this paper, several issues of the MAC layer and concepts for the definition of a new MAC protocol are presented. These concepts include synchronization, multi-user diversity, and multi-packet reception. It is shown that all these techniques can drastically increase the capacity of the MAC layer for multi-hop networks.     

CROMA – An Enhanced Slotted MAC Protocol for MANETs

TDMA based MAC protocols can provide a very good utilization of the shared radio resources, especially at high input loads, in synchronized mobile ad hoc networks (MANETs). Global positioning systems like GPS or GALLILEO should provide a very good timing accuracy for synchronization of nodes. This paper presents a new medium access protocol for mobile ad hoc networks, called CROMA. CROMA is collision-free and receiver-oriented. It operates in a slotted environment, in a dynamic and distributed way. In this protocol, receivers act as local base stations and can manage one or several communications on a single slot. Thus, sophisticated functions are allowed at higher layers. Moreover, the hidden terminal as well as the exposed terminal problems are handled by CROMA. A theoretical analysis and extensive simulations show that CROMA can reach very high throughputs.