|
Article Excerpt
1. Introduction
Many organizations are using flexibility as a weapon in an increasingly competitive economy. They have acquired the capability to offer a large variety of products at a short notice by installing sophisticated flexible resources. However, unless these resources are properly designed and operated, the benefits of increased product variety could be offset by increased costs and cycle time delays. Models for analyzing these systems for effective design and operation are therefore important. Queueing models, more specifically, polling models, enable such analysis. These models are used to analyze a system of multiple service centers (queues) attended to by one or more servers that attend to requests arriving at these centers by polling (visiting) them in a pre-specified manner.
Polling models have many other real-world applications. They are used to analyze computer networks, telephone switching systems, and manufacturing and material handling systems, to name a few. Real-world systems that can be analyzed with polling models continue to grow as new applications and technology are introduced. For example, token ring networks and networks using the fiber distributed data interface (FDDI) protocol are readily analyzed using polling models. The use of radio frequency data communication (RFDC) in warehouse management and material handling systems provides a more recent application for polling models because RFDC allows the servers (material handlers) to poll storage locations to determine whether there is any handling needed at these locations. Consequently, there is a large body of literature on polling models that has continued to grow since the late 1960s when they were first studied; see Takagi (1990, 1997) for comprehensive surveys.
In this paper, we focus on a special class of polling models known as the state dependent (SD) polling models. In the SD polling model, a single server attends to the requests waiting at the different queues, performing a setup only when there are customers waiting for service at the polled queue. Although the SD model finds many applications in the real world, it does not lend itself to easy analysis. Consequently, even though it is a more appropriate model, the SD polling model is typically approximated by the SI polling model in which the server is assumed to perform a setup (or, alternately, never performs a setup) at a polled queue regardless of its state. Such an approximation is acceptable when the system is so highly loaded that the server will always find the polled queue nonempty. However, from a practical standpoint, it is usually not desirable to utilize the server at such high levels because customers will experience unusually large waiting times.
The inherent complexity in the SD polling model arises from the fact that the analysis requires additional information to be maintained on the state of all queues in the system at all times. Most of the research on polling models has thus been confined to the state independent (SI) polling model. To our knowledge, there are very few exact procedures available for obtaining the moments of the waiting times and the number of customers for the SD polling model. Gupta and Srinivasan (1996) obtained these measures for the special case of a 2-queue model. Eisenberg (1999) presented an exact analysis for the general N queue model. Singh and Srinivasan (2001) and Srinivasan and Singh (2006) present detailed algorithms to compute these performance measures for the general N queue model. Although exact procedures exist for analyzing the SD model, these procedures are not computationally efficient. The computational effort grows exponentially with the number of queues in the system.
A number of papers provide approximate analysis of the SD model to estimate the expected waiting times and these include the work by Altman et al. (1994), Bradlow and Byrd (1987), Ferguson (1986), Gunalay and Gupta (1997), Lennon (1995), Olsen (2001), and Yehia (1998). These papers do not provide bounds on the expected waiting times and so it is difficult to determine the accuracy of these estimates. Our intent in this paper is to promote the use of SD polling models for analyzing real-world systems by presenting a fast and computationally efficient method that determines tight bounds on the values of performance measures critical to the design and evaluation of production systems. This method, the performance bound hierarchies technique, develops a hierarchy of successively more accurate bounds on the waiting time moments with the exact solution as its limit. We motivate the discussion by presenting examples of manufacturing systems that are more appropriately analyzed using the SD polling model rather than with the simpler SI polling model.
2. Manufacturing Applications
We present two different scenarios that can be modeled and analyzed with the SD model. The first scenario is discussed in greater detail.
[FIGURE 1 OMITTED]
2.1. A Material Handling System
Consider a material handling system--possibly a manual forklift, a person, or an automated guided vehicle--that moves semifinished products from three production lines in a production center to storage locations positioned close to various other production cells for further processing. The schematic of the material handling system is provided in Figure 1.
In this scenario, the server is the material handling system and the customers are the semifinished products that wait in their respective queues for the server. The server visits the stations--production lines--in a cyclic manner and polls each one to ascertain the state of that station. If there are customers waiting at the polled station, the server performs service as follows:
* stops in front of the polled station,
* picks up semifinished parts, one at a time, from the queue,
* scans the part to update necessary records maintained in a database, and
* places the part in an empty container available at that location.
This process is repeated until there are no more parts at the station. After serving (picking up, scanning, and placing in container) all the customers (semifinished parts), including customers that arrive during the service period (this is the exhaustive service discipline), the server departs from the polled station to the storage area designated for the production cell. It is assumed that the container is large enough to store all the semifinished parts present at the station. After depositing the full container at the store, the server picks up an empty container from that location and takes it back to the station. The server now places the empty container at the station and proceeds to the next station. Parts waiting at the station when the server returns are transported in the next cycle. If the polled station is empty, the server directly proceeds to the next station (in an RFDC enabled system, the server knows the state of the system immediately on arriving at the station, so there is no need for the server to come to a halt to establish the state of that station).
Let us examine the server's activities in more detail to understand the modeling nuances for this system. The time required by the server to move from station i to station i + 1 is the switchover time, denoted by [R.sub.i], i = 1,2,3, in Figure 1. The time spent moving the filled container to the respective store and to bring back an empty container is treated as the setup time, denoted by [S.sub.i] in Figure 1. This setup activity is different from the typical setup in the sense that the server executes it after completing service at the station instead of performing a setup activity before starting service. Indeed, for the SD polling model we analyze in this paper, a setup is assumed to be completed before the service period begins. However, our methodology accommodates the alternate setup activity assumed for the model of the above material handling system simply by modifying one expression in the standard SD polling model (see Remark 1 in [section]4).
2.2. A Flexible Manufacturing System
Now consider a flexible manufacturing system that processes multiple products. A workcenter in this flexible manufacturing system must have the flexibility to cater to multiple product types, each one of which might require the workcenter to perform a setup to prepare itself for service. Following the description of the model in Figure 1, it is easy to see that the exhaustive service SD model presents a very effective modeling framework for analyzing such flexible systems for their desired measures of performance such as capacity analysis, waiting time distributions, and so on. The exhaustive service strategy may, for instance, be the appropriate model to use when switchover and/or setup times are high, but it should be pointed out that more general service strategies can be analyzed within the framework of this paper. Choosing an "optimal" service strategy is, however, far from trivial. Therefore, fast algorithms that can allow us to search more easily across different strategies would be of value in this regard.
3. The Model and Preliminaries
The classical polling model considers a system in which multiple queues are served by a single server traveling from queue to queue in a prescribed sequence. Note that, in isolation, each queue is an ordinary M/G/1 queue, but because they share a single server they interact in complex ways, and their performance measures are strongly dependent on each other. We assume that customers arrive at various queues following Poisson processes and the server adopts the exhaustive service discipline (the server continues to serve customers until the queue is empty). We only consider the exhaustive service discipline in this paper, but our model can accommodate any service discipline that allows a multitype branching process interpretation (Resing 1993). We assume that the server serves the queues in a cyclic order. The methodology described below can be adapted to analyze models where the server uses a polling table (Eisenberg 1972) to switch between queues, switches between queues in a random manner (Boxma and Weststrate 1989, Kleinrock...
|
