Two-level manufacturing system performance analyser

Open queuing network is a commonly used analytical tool for modelling manufacturing systems. Parametric decomposition is a proven solution method for analysing open queuing networks and can estimate key performance measures such as work-in-process inventory, cycle time, and machine utilisation, fairly accurately. This paper presents a two-level hierarchical open queuing network model, which considers numerous features seen in a real manufacturing system including, machine set-up, material handling device setup (for example, loading and unloading operations), process as well as transfer batching, empty travel of the material handling device and machine or material handling device failures. The model first analyses a higher level open queuing network whose nodes are aggregations of a set of machines. The higher level network is solved via the parametric decomposition method and the results are then disaggregated to get lower level, e.g. machine specific, results. The motivation, algorithm and its relationship with the one-level model are discussed. Experimental results are provided to show that the two-level model provides comparable results with the one-level model in addition to its computational and managerial advantages. In addition, both are shown to provide better results than a recent method available in the literature that is based on the well-known queuing network analyser.     

具有自动装卸搬运机器人的制造单元建模与分析

针对具有自动装卸搬运机器人的制造单元，着重考虑其双重资源约束的特点，提出了该系统的有限缓冲开排队网的建模方法。根据工件的加工、装卸与搬运等工艺流程，定义该系统的排队网模型的各种状态，基于连续时间马尔可夫链，采用精确解法对该模型进行分析求解，获得系统一系列的稳态性能指标。为了验证排队网建模方法的有效性，建立其对应的仿真模型，分别采用排队网模型的数值计算与仿真模型的仿真统计2种方法求出系统的性能指标进行对比，并基于排队网模型对该制造单元的系统性能进行分析，为该类制造单元的资源配置优化和设施布局优化等问题提供重要的理论支撑。     

Optimal specialization of a maintenance workforce

This article develops an analytical method for determining an optimal specialization strategy for a maintenance workforce. The method assumes that maintenance tasks are generated by a system of statistically identical machines that experience random malfunctions and require periodic service. The impact of alternative workforce structures on system performance is evaluated with a queueing network model. Markov decision analysis is employed to determine an optimal assignment of maintenance personnel to pending tasks as the network status varies over time. A linear programming algorithm is derived to enable simultaneous optimization of specific assignment decisions and the overall workforce structure. A manufacturing example demonstrates the applicability of the method to many industrial contexts. The method is also applied to the problem of maximizing military aircraft sortie generation subject to a constraint on maintenance personnel expenditure.     

Asymmetric convolution algorithm for blocking probability calculation in full-availability group with bandwidth reservation

The paper proposes a new approximate calculation method of occupancy distribution and blocking probability in the full-availability group (FAG) with multi-rate traffic streams and bandwidth reservation. The algorithm involves calculation of system state probabilities by a convolution operation. In the paper, an effective method of calculating state probabilities in a reservation space of the system is derived. The analytical results of blocking probabilities in the FAG with bandwidth reservation, obtained on the basis of the proposed analytical method, are compared with the data obtained on the basis of other known analytical methods and with the simulation results. The accuracy of the proposed method is evaluated for different multi-rate Bernoulli (Erlang), Poisson (Engset), Pascal traffic streams. The method proposed is characterised by lower complexity than the convolution algorithm for the FAG with bandwidth reservation devised earlier.     

Modeling for flexible manufacturing systems with an FMS blocking mechanism and a BDSM job routing

We consider a Flexible Manufacturing System (FMS) which is composed of a set of workstations, a common buffer and a Material Handling System (MHS). Each workstation includes a limited input buffer, several machines and a limited output buffer. The MHS consists of several carts moving jobs among the workstations according to the process paths required by the jobs. The carts treat blocked jobs in accordance with a new blocking mechanism, called the 'FMS blocking mechanism'. The function of the common buffer is to temporarily store blocked jobs. Such an FMS is formulated as an open queueing network, in which the MHS is modeled as a central station routing jobs to the workstations. In the model, the machines process jobs with an exponentially distributed processing time, and the carts route jobs to the workstations following a 'Blocking Depended Static Markov (BDSM) job routing' with an exponentially distributed routing time and treat blocked jobs in accordance with the FMS blocking mechanism. It is shown that the equilibrium state distribution of the model has a product-form solution. The blocking probabilities are obtained by computing a fixed point problem whose solution is revealed by an iterative algorithm. Moreover, it is shown that the throughputs of the workstations are independent of the spaces on the local buffers at the workstations. Several numerical examples are presented.     

一类批处理排队网络的稳定性

在标准排队网络稳定性研究的基础上,本文通过引进批长度随机向量,确立了一类批处理排队网络的流体模型和对应的标准排队网络的流体模型。证明了在批优先排队原则下,这两类排队网络的流体模型具有相同的稳定性,为批处理排队网络的稳定性研究提供了一种有效的方法。     

面向定制生产系统的缓冲区优化配置方法

针对定制型装备制造企业中具有有限缓冲区的开排队网制造单元,其车间负荷界限即缓冲设置难以确定的问题（buffer allocation problem,BAP）,文章对每阶段具有有限缓冲区且含有多台加工设备的三阶段柔性流水车间(flexible flow shop,FFS)进行排队网建模,应用状态空间分解法对该模型进行分析求解,获得系统的一系列性能指标值。为了对该方法的有效性进行验证,对该模型设计仿真实验,并利用扩展法对模型进行求解,将数值结果进行比较分析,验证了利用该方法对FFS缓冲区进行优化配置的合理性,这对较大规模的多节点每阶段具有多台设备的流水车间负荷界限的有效设定及其规划具有参考和指导意义。     

稀疏波长变换的WDM光网络阻塞率的分析与计算

本文主要对具有稀疏波长变换的WDM全光网的阻塞率进行分析,首先提出一种模型分析了无波长变换器的L跳路径端到端阻塞率,接着对部分波长变换器的L跳路径的阻塞率进行求解,随后分析了全网的平均阻塞率。研究得到的主要结论是,波长变换器使用的有效性取决于网络的连接度。     

Queuing network analysis for a mixed voice and data communication network with end‐to‐end window flow control policy

Abstract

A Mixed Voice and Data Communication Network (MVDNET) with end‐to‐end (ETE) window flow control policy is modeled by a closed multichain queuing network. Using an approximate solution of the Mean Value Analysis (MVA) algorithm, the computational complexity of analysing a large‐scale MVDNET and various commodities is dramatically reduced by several orders of magnitude over that required by traditional product‐form solution. We consider the problems concerned with the choice of window size, the effect of voice interruption, the number of voice‐grade (VG) channels per internode link and the selection of appropriate packet length. It is shown that the analytic results are very close to the simulation ones using GPSS language, and that the extensive MVA algorithm is a practical and valuable tool for solving the MVDNET analytical model with ETE window flow control policy.     

An analysis of the ceiling height requirement for a large-scale semiconductor fab

This paper proposes the proposition that the fab ceiling height may become a bottleneck for throughput in a large-scale semiconductor fab. To justify the proposition, we propose a systematic approach for the design of the fab ceiling height. In this approach, we develop a queuing network model to evaluate the cycle time performance of a fab design under a target throughput. This queuing network model is adapted from Connor et al. [1996. A queueing network model for semiconductor manufacturing. IEEE Transactions on Semiconductor Manufacturing, 9 (3), 412–427] by additionally treating the transportation facilities as finite-capacity resources. Numerical experiments were carried out. The results indicate that a large-scale fab with an inappropriate ceiling height may limit the installation of transportation capacity, which, in turn, limits the utilisation of tool capacity, and thus lowers the fab throughput that can be achieved.     

A heuristic travel time model for random storage systems using closest open location load dispatching

A heuristic method is proposed for estimating travel times in unit load random storage systems where incoming loads are dispatched to the closest available storage positions. A queuing model representation is used where servers correspond to storage positions and the service rate is based on the turnover distribution of stored loads. The resultant state distribution is applied to approximate storage position occupancy probabilities useful for generating storage and retrieval travel time estimates. Computational results suggest that the heuristic procedure yields smaller errors in random storage travel time estimates than alternative models.     

A genetic algorithm and queuing theory based methodology for facilities layout problem

Facilities layout, being a significant contributor to manufacturing performance, has been studied many times over the past few decades. Existing studies are mainly based on material handling cost and have neglected several critical variations inherent in a manufacturing system. The static nature of available models has reduced the quality of the estimates of performance and led to not achieving an optimal layout. Using a queuing network model, an established tool to quantify the variations of a system and operational performance factors including work-in-process (WIP) and utilisation, can significantly help decision makers in solving a facilities layout problem. The queuing model utilised in this paper is our extension to the existing models through incorporating concurrently several operational features: availability of raw material, alternate routing of parts, effectiveness of a maintenance facility, quality of products, availability of processing tools and material handling equipment. On the other hand, a queuing model is not an optimisation tool in itself. A genetic algorithm, an effective search process for exploring a large search space, has been selected and implemented to solve the layout problem modelled with queuing theory. This combination provides a unique opportunity to consider the stochastic variations while achieving a good layout. A layout problem with unequal area facilities is considered in this paper. A good layout solution is the one which minimises the following four parameters: WIP cost, material handling cost, deviation cost, and relocation cost. Observations from experimental analysis are also reported in this paper. Our proposed methodology demonstrates that it has a potential to integrate several related decision-making problems in a unified framework.     

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     

Optimisation of production and subcontracting strategies

We consider the problem of optimising production and subcontracting decisions in a supply chain manufacturing engineered products. The supply chain manager can use a combination of internal production capacities, available capacity at qualified subcontractors, make capital investments and process improvements to minimise costs associated with production and penalties for not meeting desired operational metrics. We formulate this as an optimisation problem that requires simultaneous solution of a mathematical programming problem and queuing network model. We propose an efficient iterative approach to solve this problem and conduct numerical studies to demonstrate the effectiveness of the approach.     

Queuing network analysis approach for estimating the sizes of the time buffers in Theory of Constraints-controlled production systems

The present paper describes an open queuing network modelling approach to estimate the size of the time buffers in production systems controlled by the Theory of Constraints philosophy. Workstations in the production network are modelled as GI/G/m queues and a queuing network analysis multiproduct open queuing network modelling method is used to estimate the average flow time to the time buffer origin and the standard deviation of flow time. Using these two values together with an assumption of normally distributed flow times and a chosen service level, the final time buffer length is determined. The queuing network analysis method has been modified to enable the modelling of production networks with machine failures, batch service and varying transfer batch sizes. The modelling approach has also been incorporated in a computerized tool that uses product specific information such as bill-of-material and routing data, and production network information such as resource data to estimate the sizes and location of the necessary time buffers for each product. Simulation experiments indicate that the procedure is sufficiently accurate to provide an initial quick estimate of the needed time buffer lengths at the design stage of the line.     

Events Defined by Duration and Severity,With an Application to Network Reliability

Communications networks are highly reliable and almost never experience widespread failures. But from time to time performance degrades and the probability that a call is blocked or fails to reach its destination jumps from nearly 0 to an unacceptable level. High but variable blocking may then persist for a noticeable period of time. Extended periods of high blocking, or events, can be caused by congestion in response to natural disasters, fiber cuts, equipment failures, and software errors, for example. Because the consequences of an event depend on the level of blocking and its persistence, lists of events at specified blocking and duration thresholds, such as 50% for 30 minutes or 90% for 15 minutes, are often maintained. Reliability parameters at specified blocking and duration thresholds, such as the mean number of events per year and mean time spent in events, are estimated from the lists of reported events and used to compare network service providers, transmission facilities, or brands of equipment, for example. This article shows how data obtained with two-stage sampling can be used to estimate blocking probabilities as a function of time. The estimated blocking probabilities are then used to detect and characterize events and to estimate reliability parameters at specified blocking and duration thresholds. Our estimators are model-free, except for one step in a sampling bias correction, and practical even if there are hundreds of millions of observations. Pointwise confidence intervals for reliability parameters as a function of blocking and duration thresholds are built using a kind of “partial bootstrapping” that is suitable for very large sets of data. The performance of the algorithm for event detection and the estimators of reliability parameters are explored with simulated data. An application to comparison of two network service providers is given in this article, and possible adaptations for other monitoring problems are sketched.     

Comparative performance analysis of versions of TCP in a local network with a mobile radio link

The scenario is that a bulk data transfer is being performed over a TCP connection, from a host on a local area network (LAN) to a mobile host attached to the LAN by a radio link. In an earlier work we had assumed that packet losses in a TCP connection over a radio link are statistically independent. In this paper, we extend this analysis to a Rayleigh fading link, which we model by a two-state Markov model. The bulk throughputs of TCP-OldTahoe and TCP-Tahoe are compared with and without fading, for various average signal-to-noise ratios. We also study the performance with a link protocol on the wireless link, and study the effect of varying the link packet size, the number of link packet attempts, and the vehicle speed. For the parameters of the BSD UNIX implementation, over a 1.5 Mbps wireless link, we find that, with fading, a signal-to-noise ratio of at least 30 dB is required to get reasonable throughput with TCP Tahoe or OldTahoe; this corresponds to at least 100 times more power than is needed without fading. For fixed signal-to-noise ratio, as the vehicle speed varies there are roughly 3 regions of performance: at very low speeds (pedestrian speeds) the throughput is very good; at low vehicular speeds the throughput deteriorates, and again becomes very good at higher vehicle speeds. The speeds corresponding to the various regions depend on the parameters of the link protocol. This work was done while the first author was on Sabbatical at WINLAB, Rutgers University     

Assessing the reliability and the expected performance of a network under disaster risk

In a disaster situation, functionality of an infrastructure network is critical for effective emergency response. We evaluate several probabilistic measures of connectivity and expected travel time/distance between critical origin–destination pairs to assess the functionality of a given transportation network in case of a disaster. The input data include the most likely disaster scenarios as well as the probability that each link of the network fails under each scenario. Unlike most studies that assume independent link failures, we model dependency among link failures and propose a novel dependency model that incorporates the impact of the disaster on the network and at the same time yields tractable cases for the computation of the probabilistic measures. We develop algorithms for the computation of the measures and utilize a Monte Carlo simulation algorithm for the intractable cases. We present a case study of the Istanbul highway system under earthquake risk, and compare different dependency structures computationally.     

自相似业务下光分组交换边缘节点排队方案性能分析

研究了自相似业务下光分组交换网中边缘节点的工作性能,建立了轮询机制下的排队模型,分析了平均组装／发送时延与最大汇聚分组长度等参数的关系。研究表明：平均时延与最大汇聚长度及边缘节点数目成线性关系,与发射速率成反比关系,随业务强度的增加而增大。所得结论具有轮询机制的共性,为进一步研究其他排队方案奠定了基础。     

Modeling idiosyncratic properties of collaboration networks revisited

A study on the network characteristics of two collaboration networks constructed from the ACM and DBLP digital libraries is presented. Different types of generic network models and several examples are reviewed and experimented on re-generating the collaboration networks. The results reveal that while these models can generate the power-law degree distribution sufficiently well, they are not able to capture the other two important dynamic metrics: average distance and clustering coefficient. While all current models result in small average distances, none shows the same tendency as the real networks do. Furthermore all models seem blind to generating large clustering coefficients. To remedy these shortcomings, we propose a new model with promising results. We get closer values for the dynamic measures while having the degree distribution still power-law by having link addition probabilities change over time, and link attachment happen within local neighborhood only or globally, as seen in the two collaboration networks.