Search

With the increasing reliance on cloud computing as the foundational manufacturing systems with intricate dynamics, featuring multiple service areas, varying job arrival rates, diverse service requirements, and the interplay of failures and impatience, significant analytical challenges arise. Queueing networks offer a powerful stochastic modeling framework to capture such complex dynamics. This paper develops a novel, exhaustive queueing model for a finite-capacity redundant multi-server system operating in a multi-phase random environment. The proposed model uniquely integrates real-world factors, including server breakdowns and repairs, waiting servers, synchronous working vacations, and state dependent balking and reneging, into a single queueing model, representing a significant advancement in the field. Using the matrix-analytic method, we establish the steady-state solution and derive key performance metrics. Numerical experiments and sensitivity analyses elucidate the impact of system parameters on performance measures. Additionally, a cost model is formulated, enabling cost optimization analysis using direct search method and Particle Swarm Optimization (PSO) to identify efficient operating configurations. [Display omitted] • Analytical framework for finite capacity redundant multi-server queue in multi-phase environment. • Matrix analytic method calculates steady-state probabilities to assess system performance. measures. • Through sensitivity analysis, key cost variables are identified, aiding decision-making. • Optimizing the cost function by merging Direct Search Method (DSM) and Particle Swarm Optimization (PSO). [ABSTRACT FROM AUTHOR]

• QN-ACTR-SA is a model designed to simulate driver Situation Awareness (SA). • Utilizes QN-ACTR framework and SEEV model to simulate drivers SA. • Interacts with simulators for realistic predictions. • Validated against empirical data from drivers in complex and easy driving conditions. The goal of this research is to computationally model and simulate the situation awareness (SA) of drivers. A computational model in a cognitive architecture was developed that can interact with a driving simulator to infer quantitative predictions of drivers' SA. The model uses the Queueing Network Adaptive Control of Thought-Rational (QN-ACTR) framework as a foundation and integrates a dynamic visual sampling model (SEEV) to create QN-ACTR-SA, which simulates attention allocation patterns of human drivers at SA Level 1 (i.e., perception of critical elements). QN-ACTR-SA also incorporates a driver model that can interact with a driving simulator. A validation study was conducted to determine whether Level 1 SA results produced with the QN-ACTR-SA model correspond to empirical data collected from human drivers (14 participants) for the same tasks. Both QN-ACTR-SA and human participants were probed for SA using two approaches: within-task queries using the Situation Awareness Global Assessment Technique (SAGAT) and post-experiment questions. A comparative assessment demonstrated that QN-ACTR-SA could reasonably simulate drivers' Level 1 SA for two driving conditions: easy (with few vehicles and signboards) and complex (with dense traffic and signboards). QN-ACTR-SA fit for human SAGAT scores (possible range 0–100) resulted in a mean absolute percentage error (MAPE) of 5.0% and the root means square error (RMSE) of 3.5. Model fit for post-experiment human SA results was MAPE of 6.7% and RMSE of 6.1. Limitations of QN-ACTR-SA as a predictive model and areas of future research are discussed. [ABSTRACT FROM AUTHOR]

Much research has focused on task offloading in fog-enabled IoT networks. However, there is an important offloading issue that has hardly been addressed—the impact of different virtualization modes on task response (TR) time. In the present article, we bridge this gap, introducing three virtualization modes, and characterizing the TR time under each. In each mode the virtual machines (VM) at the fog are customized differently, leveraging VM elasticity. In the perfect virtualization mode, the VM is customized to match exactly the computational load of the incoming task. This ensures that each task, regardless of which VM it goes to, will have the same service time. In the semiperfect virtualization mode, a less stringent, thus more practical, alternative, the VM is customized to match roughly the computational load of the incoming task. This results in a uniformly distributed task service time. Finally, in the baseline virtualization mode, the VM is customized to just be fast, with no regard to the computational load of the incoming task. This mode, which just re-scales the processing time of the task, is the default in existing research, and is re-introduced here for only comparison purposes. We characterize the TR time for the three modes leveraging M/G/1 and M/G/m queueing models, with the queueing stability condition identified for each mode. The obtained analytical results are successfully validated by discrete event Monte Carlo simulation. The numerical results show that the first mode results in the shortest TR time, followed by the second mode, then the third mode. That is, if virtualization is managed adequately, significant improvement in TR time can be gained. [ABSTRACT FROM AUTHOR]

In the paper, a new method was presented using queueing theory models in order to ensure an optimal production department size, optimized production costs and optimal provision. Queueing/waiting mathematical models represent the development matrix for an experimental algorithm and implicitly numerical approach, both successfully applied (and confirmed in practice) in a production section design for a real industrial engineering unit with discussed method technological flow and equipment schemes compatibility. The total costs for a queueing system with S servers depend on the number of servers. The problem of minimizing cost in terms of S was the main aim of the paper. In order to solve it, we estimated all the variables of the system that influence the cost using the Monte Carlo method. For a Jackson queueing network, the involved linear system has good properties such that it can be solved by iterative methods such as Jacobi and Gauss–Seidel. [ABSTRACT FROM AUTHOR]

Stream processing is an emerging in-memory computing paradigm to handle massive amounts of real-time data. It is vital to have a mechanism to propose proper parallelism for the operators to handle streaming data efficiently. Previous research has mostly focused on parallelism optimization with infinite buffers; however, the topology's quality of service is severely affected by network buffers. Thus, in this paper, we introduce an extended queueing network to model the relationship between the parallelism and tuple's average sojourn time with limited buffers. Based on this model, we also propose greedy algorithms to calculate the optimal parallelism for both the minimum latency and maximum throughput with resource constraints. To fairly evaluate the performance of different models, a random parameter generator for the streaming topology is presented. Experiments show that the extended queuing model may properly forecast performance. Compared to the state-of-the-art method, the proposed algorithms reduce the median total sojourn time by 3.74 times and increase the average maximum sustainable throughput by 1.69 times. [ABSTRACT FROM AUTHOR]

To share limited, large-capacity resources, the high-performance computing field provides services by allocating available resources to jobs through batch job schedulers. Therefore, it is natural that a queue waiting time occurs until the resources are available if resources are not sufficient. The prediction of queue waiting time is very useful to improve overall resource utilization. However, the queue waiting time is very difficult to predict because it is significantly affected by the many factors such as applied scheduling algorithm and characteristics of the executed job. In this study, a method of predicting queue waiting time using only the historical log data created by the batch job scheduler is examined. Specifically, a method of predicting queue waiting time based on a hidden Markov model is proposed. It has the following three stages. First, outliers are removed by applying the outlier detection algorithm using a statistics-based parametric method. Second, the parameters of the hidden state are estimated using the observed queue waiting time sequence based on the historical job log. Third, the queue waiting interval at time t + 1 is provided using the estimated parameters at time t. Comparing the prediction accuracy with those of the other prediction methods, experimental results show that the proposed algorithm improves the prediction accuracy by up to 60%. [ABSTRACT FROM AUTHOR]

Standard server assignment policies for multi-server queueing stations include the noncollaborative policy, where the servers work in parallel on different jobs; and the fully collaborative policy, where the servers work together on the same job. However, if each job can be decomposed into subtasks with no precedence relationships, then we consider a form of server coordination named task assignment where the servers work in parallel on different subtasks of the same job. We identify the task assignment policy that maximizes the long-run average throughput of a queueing station with finite internal buffers when blocked servers can be idled or reassigned to either replace or collaborate with other servers on unblocked subtasks. We then compare the server coordination policies and show that the task assignment is best when the servers are highly specialized; otherwise, the fully collaborative or noncollaborative policies are preferable depending on whether the synergy level among the servers is high or not. We also provide numerical results that quantify our previous comparison. Finally, we address buffer allocation in longer lines where there are precedence relationships between some of the tasks, and present numerical results that suggest our comparisons for one queueing station generalize to longer lines. [ABSTRACT FROM AUTHOR]

This paper considers the customers' equilibrium and socially optimal joining–balking behavior in a single-server Markovian queue with a single working vacation and Bernoulli interruptions. The model is motivated by practical service systems where the service rate can be adjusted according to whether or not the system is empty. Specifically, we focus on a single-server queue in which the server's service rate is reduced from a regular to a lower one when the system becomes empty. This lower rate period is called a working vacation for the server which may represent that part of the service facility is under a maintenance process or works on other non-queueing job, or simply for saving the energy (for a machine server case). In this paper, we assume that the working vacation period is terminated after a random period or with probability p after serving a customer in a non-empty system. Such a system is called a queue with single working vacation and Bernoulli interruptions. Customers are strategic and can make choice of joining or balking based on different levels of system information. We consider four scenarios: fully observable, almost observable, almost unobservable, and fully unobservable queue cases. Under a reward-cost structure, we analyze the customer's equilibrium and social-optimal strategies. In addition, the effects of system parameters on optimal strategies are illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, a finite-source retrial queueing system with twoway communication is investigated with the help of a simulation program of own. If a randomly arriving request from the finite-source finds the single server idle its service starts immediately, otherwise it joins an orbit from where it generates retrial/repeated calls after a random time. To increase the utilization of the server when it becomes idle after a random time an outgoing request is called for service from an infinity source. Upon its arrival if the server is busy, it goes to a buffer and when the server becomes idle again its service starts immediately. requests arriving from the finite-source and orbit are referred to as primary or incoming ones while requests called from the infinite source are referred to as secondary or outgoing requests, respectively. The service times of the primary and secondary requests are supposed to be random variables having different distributions. However, randomly catastrophic failures may happen to all the requests in the system, that is from the orbit, the service unit, and the buffer. In this case, the primary requests return to the finite-source, and the secondary ones are lost. The operation of the system is restored after a random time. Until the restoration is finished no arrivals and service take place in the system. All the above-mentioned times are supposed to be independent random variables. The novelty of this paper is to perform a sensitivity analysis of the failure and restoration/repair times on the main characteristics to illustrate the effect of different distributions having the same average and variance value. Our aim is to determine the distribution of the number of requests in the system, the average response time of an arbitrary primary request without successful service, also the average response time of an arbitrary and successfully served primary request, the total utilization of the service unit, or the probability that a primary request leaves the system without successful service because of a catastrophic event. Results are illustrated graphically obtained by our simulation program. [ABSTRACT FROM AUTHOR]

The paper "Fluid-Diffusion-Hybrid (FDH) Approximation" proposes a new heavy-traffic asymptotic regime for a two-class priority system in which the high-priority customers require substantially larger service times than the low-priority customers. In the FDH limit, the high-priority queue is a diffusion, whereas the low-priority queue operates as a (random) fluid limit, whose dynamics are driven by the former diffusion. A characterizing property of our limit process is that, unlike other asymptotic regimes, a non-negligible proportion of the customers from both classes must wait for service. This property allows us to study the costs and benefits of de-pooling, and prove that a two-pool system is often the asymptotically optimal design of the system. We consider a large service system with two customer classes that are distinguished by their urgency and service requirements. In particular, one of the customer classes is considered urgent, and is therefore prioritized over the other class; further, the average service time of customers from the urgent class is significantly larger than that of the nonurgent class. We therefore refer to the urgent class as "slow," and to the nonurgent class as "fast." Due to the complexity and intractability of the system's dynamics, our goal is to develop and analyze an asymptotic approximation, which captures the prevalent fact that, in practice, customers from both classes are likely to experience delays before entering service. However, under existing many-server limiting regimes, only two of the following options can be captured in the limit: (i) either the customers from the prioritized (slow) customer class do not wait at all, or (ii) the fast-class customers do not receive any service. We therefore propose a novel Fluid-Diffusion Hybrid (FDH) many-server asymptotic regime, under which the queue of the slow class behaves like a diffusion limit, whereas the queue of the fast class evolves as a (random) fluid limit that is driven by the diffusion process. That FDH limit is achieved by assuming that the service rate of the fast class scales with the system's size, whereas the service rate of the slow class is kept fixed. Numerical examples demonstrate that our FDH limit is accurate when the difference between the service rates of the two classes is sufficiently large. We then employ the FDH approximation to study the costs and benefits of de-pooling the service pool, by reserving a small number of servers for the fast class. We prove that, in some cases, a two-pool structure is the asymptotically optimal system design. [ABSTRACT FROM AUTHOR]

We study an inventory system with multiple supply sources and expediting options. The replenishment lead times from each supply source are stochastic, representing congestion and disruption. We construct a family of smart ordering and expediting policies that utilize real-time supply information. Such dynamic policies are generally difficult to evaluate, because the corresponding supply system is a tandem queue with state-dependent arrivals and routing, whose queue-length steady-state distribution is usually not in product form. Our main result is to identify two appealing special cases of the general policy, Policy-M and Policy-E, which possess simple product-form solutions and lead to closed-form performance measures. Policy-M retains full sourcing flexibility, but ignores upstream congestion in making expediting decisions. Policy-E only orders from the normal, farthest source, but makes expediting decisions based on both upstream and downstream information. A numerical study shows that the best Policy-M leads to a lower average cost than the best Policy-E in almost all cases. Also, implementing the best Policy-M parameters, the general policy only performs slightly better than Policy-M. These observations reveal the value of combining sourcing flexibility with some, but limited, dynamic expediting. Our findings are equally applicable to the equivalent tandem queue. They thus may aid dynamic routing and expediting decisions for online retailers and logistics providers, among others. [ABSTRACT FROM AUTHOR]

The close-in weapon system (CIWS) is a combat system that faces a complex environment full of dynamic and unknown challenges, whose construction and planning require a systematic design method. Multiliving agent (MLA) theory is a methodology for the combat system design, which uses the livelihood degree to evaluate the multi-dimensional long-term operational effectiveness of the system; whereas, there is still no uniform quantization framework for the livelihood degree, and the adjustment methods of livelihood degree need to be further improved. In this paper, we propose the uniform quantization framework for the livelihood degree and detailed discuss the methods of livelihood adjustment. Based on the MLA theory, the multi-dimensional operational effectiveness of the missile-gun integrated weapon system (MGIWS) is analyzed, and the long-term combat effectiveness against the saturation attack is assessed. Furthermore, the planning problem of the equipment deployment and configuration is investigated. Two objectives, including the overall livelihood degree and cost-effectiveness (CE), are proposed, and the optimization method based on genetic algorithm (GA) is studied for the planning problem. [ABSTRACT FROM AUTHOR]

We consider a semi-open queueing network (SOQN), where one resource from a resource pool is needed to serve a customer. If on arrival of a customer some resource is available, the resource is forwarded to an inner network to complete the customer's order. If no resource is available, the new customer waits in an external queue until one becomes available ("backordering"). When a resource exits the inner network, it is returned to the resource pool. We develop a new solution approach. In a first step we modify the system such that new arrivals are lost if the resource pool is empty ("lost customers"). We adjust the arrival rate of the modified system such that the throughputs in all nodes of the inner network are pairwise identical to those in the original network. Using queueing theoretical methods, in a second step we reduce this inner network to a two-station system including the resource pool. For this two-station systems, we invert the first step and obtain a standard SOQN which can be solved analytically. We apply our results to storage and delivering systems with robotic mobile fulfilment systems (RMFSs). Instead of sending pickers to the storage area to search for the ordered items and pick them, robots carry shelves with ordered items from the storage area to picking stations. We model the RMFS as an SOQN to determine the minimal number of robots. [ABSTRACT FROM AUTHOR]

We provide two examples of strictly subcritical multiclass queueing networks which are unstable under the shortest remaining processing time (SRPT) service protocol. Both of them are reentrant lines with two servers and eight customer classes. The customer service times in our first system are deterministic, yielding an example of an unstable shortest remaining expected processing time (SERPT) network. In the second one, the service times in one customer class are randomized. Both our examples show also system instability under the shortest job first (SJF) discipline. A simulation study of robustness of our results with respect to changes in the customer interarrival and service times is also provided. Our results indicate that size-based service policies may not use the available resources efficiently in a multiserver network setting and in fact cause instability effects. This is in sharp contrast with their satisfactory performance for single-server queues. [ABSTRACT FROM AUTHOR]

The age of information (AoI) metric was proposed to measure the freshness of messages obtained at the terminal node of a status updating system. In this paper, the AoI of a discrete time status updating system with probabilistic packet preemption is investigated by analyzing the steady state of a three-dimensional discrete stochastic process. We assume that the queue used in the system is B e r / G e o / 1 / 2 * / η , which represents that the system size is 2 and the packet in the buffer can be preempted by a fresher packet with probability η. Instead of considering the system's AoI separately, we use a three-dimensional state vector (n , m , l) to simultaneously track the real-time changes of the AoI, the age of a packet in the server, and the age of a packet waiting in the buffer. We give the explicit expression of the system's average AoI and show that the average AoI of the system without packet preemption is obtained by letting η = 0 . When η is set to 1, the mean of the AoI of the system with a B e r / G e o / 1 / 2 * queue is obtained as well. Combining the results we have obtained and comparing them with corresponding average continuous AoIs, we propose a possible relationship between the average discrete AoI with the B e r / G e o / 1 / c queue and the average continuous AoI with the M / M / 1 / c queue. For each of two extreme cases where η = 0 and η = 1 , we also determine the stationary distribution of AoI using the probability generation function (PGF) method. The relations between the average AoI and the packet preemption probability η , as well as the AoI's distribution curves in two extreme cases, are illustrated by numerical simulations. Notice that the probabilistic packet preemption may occur, for example, in an energy harvest (EH) node of a wireless sensor network, where the packet in the buffer can be replaced only when the node collects enough energy. In particular, to exhibit the usefulness of our idea and methods and highlight the merits of considering discrete time systems, in this paper, we provide detailed discussions showing how the results about continuous AoI are derived by analyzing the corresponding discrete time system and how the discrete age analysis is generalized to the system with multiple sources. In terms of packet service process, we also propose an idea to analyze the AoI of a system when the service time distribution is arbitrary. [ABSTRACT FROM AUTHOR]

This paper develops an explicit characterization and computation of the queueing processes associated with finite buffered multiclass fluid queues and their tandem networks under strict priority and with PieceWise Constant Rate (PWCR) inputs which arise in the performance analysis of communication networks. Analytical and exact computational solutions are developed for accepted arrival, fluid level and departure processes which allow solutions for all other queueing processes. A decomposition of the multiclass queue into a hierarchical sequence of single class queues, termed Virtual Queues, is established and the solutions of each class of the original queue are computed from those of the Virtual Queues taking into account the loosely coupled dynamics of these Virtual Queues. A uniform time sampling sequence, dynamically constructed from the input rate change instances and the boundary hitting times, is employed to develop the iterative transient sample path solutions of all the queueing processes. The processes of a multiclass queue with PWCR inputs are shown to be PWCR processes. The computational solution is extended to tandem networks of multiclass queues in which a class can have different static priorities along its path. The developed algorithm is applied to solve a tandem communication network with three-state Markov modulated voice source inputs. A parametric study of the voice network in terms of long-term time-averaged behaviour of its queueing processes is carried out. [ABSTRACT FROM AUTHOR]

We present analytic expressions (in terms of roots of the underlying characteristic equation) for the steady-state distributions of the number of customers for the finite-state queueing model G e o X / G / 1 / N + 1 with partial-batch rejection policy. We obtain the system-length distributions at a service-completion epoch by applying the imbedded Markov chain technique. Using the roots of the related characteristic equation, the method leads to giving a unified approach for solving both finite- and infinite-buffer systems. We find relationships between system-length distributions at departure, random, and arrival epochs using discrete renewal theory and conditioning on the system states. Based on these relationships, we obtain various performance measures and provide numerical results for the same. We also perform computational analysis and compare our results with respect to the solution obtained by solving a linear system of equations in terms of running times. [ABSTRACT FROM AUTHOR]

The paper is devoted to the analysis of queueing systems in the context of the network and communication theory (called a multi-server multi-core open queueing network). The ob ject of this research on the queueing theory is theorems about the Functional Strong Laws of Large Numbers (FSLLN) in multi-server multi-core open queueing networks, working under overload heavy traffic conditions. FSLLN is known as a fluid limit or fluid approximation. In this paper, FSLLN are proved for extreme values of important probabilistic characteristics of the multi-server multicore open queueing network, investigated as well as the virtual waiting time of a job and the queue length of jobs. As applications of the proved theorems Little's laws in a multi-server multi-core open queueing network are presented. [ABSTRACT FROM AUTHOR]

A notorious problem in queueing theory is to compute the worst possible performance of the GI/G/1 queue under mean-dispersion constraints for the interarrival- and service-time distributions. We address this extremal queue problem by measuring dispersion in terms of mean absolute deviation (MAD) instead of the more conventional variance, making available methods for distribution-free analysis. Combined with random walk theory, we obtain explicit expressions for the extremal interarrival- and service-time distributions and, hence, the best possible upper bounds for all moments of the waiting time. We also obtain tight lower bounds that, together with the upper bounds, provide robust performance intervals. We show that all bounds are computationally tractable and remain sharp also when the mean and MAD are not known precisely but are estimated based on available data instead. Summary of Contribution: Queueing theory is a classic OR topic with a central role for the GI/G/1 queue. Although this queueing system is conceptually simple, it is notoriously hard to determine the worst-case expected waiting time when only knowing the first two moments of the interarrival- and service-time distributions. In this setting, the exact form of the extremal distribution can only be determined numerically as the solution to a nonconvex nonlinear optimization problem. Our paper demonstrates that using mean absolute deviation (MAD) instead of variance alleviates the computational intractability of the extremal GI/G/1 queue problem, enabling us to state the worst-case distributions explicitly. [ABSTRACT FROM AUTHOR]

Utilization data is a kind of time-series data that consists of the proportion of the system's busy time in a fixed time interval. Utilization data can indicate the status of servers in a computer system, such as CPU utilization. Unfortunately, estimating model parameters from utilization data is challenging due to the inability to obtain the exact job arrival time and service time. Moreover, the maximum likelihood estimation (MLE) method tends to be sensitive, which may cause an overfitting problem. In this paper, a hierarchical Bayes (HB) based approach is proposed to estimate the parameters of queueing systems from utilization data. Specifically, a time non-homogeneous queueing system Mt/M/1/K whose job arrival follows a non-homogeneous Poisson process (NHPP) is supposed. Then, a series of homogeneous Poisson processes (HPP) is approximated to simplify the NHPP. Finally, the HB method is applied to estimate parameters of the Mt/M/1/K to address the sensitive issue of the MLE method. In numerical experiments, the effectiveness of the proposed HB-based approach with CPU utilization data is validated. In addition, the statistical properties of estimated parameters with MLE and HB are also studied in experiments. [ABSTRACT FROM AUTHOR]

Software‐defined wide area network (SD‐WAN) is part of wider technologies of software‐defined networking (SDN). SDN is one of the pivotal network management approaches that abstracts the underlying network infrastructure away from its applications. SDN allows for the centralisation of network intelligence. That allows higher network automation, the simplification of operations, the provisioning, the monitoring, and the troubleshooting. These days, data volume that enterprises and users make is growing rapidly and continuously. As a result, wide area networks are growing increasingly and they are becoming very complicated to manage and monitor using traditional tools. So, many enterprises are interested in developing SD‐WAN and benefiting from its advantages. To achieve this goal, a proposed model for the SD‐WAN network will be presented based on the queueing theory; then, the proposed model will be analysed using the Quasi‐birth–death approach to evaluate traffic behaviour of a proposed queueing model for Poisson distribution in the SD‐WAN. Moreover, it compares Poisson to phase type distribution via calculating some parameters that influence traffic behaviour of those distributions in the SD‐WAN. The analysis results indicate that the proposed queueing model displays a more accurate SD‐WAN controller performance than the existing ones. [ABSTRACT FROM AUTHOR]

Copyright of Cybernetics & Systems Analysis / Kibernetiki i Sistemnyj Analiz is the property of V.M. Glushkov Institute of Cybernetics of NAS of Ukraine and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The optimal management of shared vehicle systems, such as bike-, scooter-, car-, or ride-sharing, is more challenging compared with traditional resource allocation settings because of the presence of spatial externalities—changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using Markovian models to design pricing and other control policies is computationally difficult because the resulting optimization problems are high dimensional and nonconvex. In our work, we design a framework that provides near-optimal policies, for a range of possible controls, that are based on applying the possible controls to achieve spatial balance on average. The optimality gap of these policies improves as the ratio between supply and the number of locations increases and asymptotically goes to zero. Optimizing shared vehicle systems (bike-/scooter-/car-/ride-sharing) are more challenging compared with traditional resource allocation settings because of the presence of complex network externalities—changes in the demand/supply at any location affect future supply throughout the system within short timescales. These externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze such systems. However, using such models to design pricing and other control policies is computationally difficult because the resulting optimization problems are high dimensional and nonconvex. To this end, we develop a rigorous approximation framework for shared vehicle systems, providing a unified approach for a wide range of controls (pricing, matching, rebalancing), objective functions (throughput, revenue, welfare), and system constraints (travel times, welfare benchmarks, posted-price constraints). Our approach is based on the analysis of natural convex relaxations and obtains as special cases existing approximate optimal policies for limited settings, asymptotic optimality results, and heuristic policies. The resulting guarantees are nonasymptotic and parametric and provide operational insights into the design of real-world systems. In particular, for any shared vehicle system with n stations and m vehicles, our framework obtains an approximation ratio of 1 + (n − 1) / m , which is particularly meaningful when m/n, the average number of vehicles per station, is large, as is often the case in practice. [ABSTRACT FROM AUTHOR]

In this paper, we study an N server fork-join queue with nearly deterministic arrival and service times. Specifically, we present a fluid limit for the maximum queue length as N → ∞. This fluid limit depends on the initial number of tasks. In order to prove these results, we develop extreme value theory and diffusion approximations for the queue lengths. [ABSTRACT FROM AUTHOR]

A fork-join processing network is a queueing network in which tasks associated with a job can be processed simultaneously. Fork-join processing networks are prevalent in computer systems, healthcare, manufacturing, project management, justice systems, and so on. Unlike the conventional queueing networks, fork-join processing networks have synchronization constraints that arise because of the parallel processing of tasks and can cause significant job delays. We study scheduling in fork-join processing networks with multiple job types and parallel shared resources. Jobs arriving in the system fork into arbitrary number of tasks, then those tasks are processed in parallel, and then they join and leave the network. There are shared resources processing multiple job types. We study the scheduling problem for those shared resources (i.e., which type of job to prioritize at any given time) and propose an asymptotically optimal scheduling policy in diffusion scale. [ABSTRACT FROM AUTHOR]

The paper proposes an optimized and energy-efficient Ad Hoc On-Demand Distance Vector (AODV) routing protocol for Mobile Ad Hoc Network (MANET) based on dynamic forwarding probability, in which the Route Request (RREQ) packets are randomly controlled to increase the network lifetime and reduce packet loss in the flooding algorithm. The results are assessed using various network performance factors after implementing and integrating them into Network Simulator (NS2). According to the simulation findings, the proposed technique effectively reduced RREQ propagation messages. It is more efficient, has a longer network lifetime, and uniformly utilizes nodal residual energy, enhancing network throughput and minimizing routing overhead when compared to regular and modified AODV protocols. [ABSTRACT FROM AUTHOR]

We have recently witnessed a number of new software-defined paradigms of VANET in what is referred to as software-defined vehicle networks (SDVN). In order to evaluate the performance of these new proposals and architectures, analytical and simulation models are needed. In this paper, we propose an analytical model based on ON-OFF queueing networks under exponential and general service time distributions. The model can be used to evaluate the performance of SDVNs and takes into account the effect of mobility such as, hand overs, node turning ON/OFF, node going temporary out of coverage, and intermittent connections. This mobility effect was modelled as a queueing station with exponentially random ON-OFF service times, where traffic arrives according to a Poisson random process during the exponentially random ON period and the service time is exponentially distributed. However, during the OFF period the service time is exponentially distributed but with lower rates. We studied the ON-OFF queueing behaviour extensively for both finite-capacity and infinite-capacity queues. Three hypothetical SDVN scenarios were considered, taking into account the effect of mobility and the large number of connected nodes. Results were cross-validated with those obtained by a simulation model. These tools will be valuable for researchers interested in getting quantitative answers for their SDVN architectures. [ABSTRACT FROM AUTHOR]

A combined location-routing-inventory system (CLRIS) in a three-echelon supply chain network is studied with environmental considerations. Specifically, a bi-objective mixed integer programming model is formulated for the CLRIS to deal with the trade-offs between the total cost and the carbon-capped difference (CCD). A multi-objective particle swarm optimization (MOPSO) heuristic solution procedure is developed and implemented to solve the bi-objective mixed integer programming problem. The bi-objective mixed integer programming model and the MOPSO heuristic procedure are applied to a real-life problem as an illustrative example. The approximate nondominated frontier formed by solutions not dominated by others can be used for the decision makers to make trade-offs between the total cost and the CCD. Sensitivity analyses are conducted, and the relationship among the carbon cap, CCD, the total cost and the carbon prices are examined, and relevant managerial insights are provided. Comparisons with other existing algorithms show that the MSPSO heuristic procedure has very good performance. [ABSTRACT FROM AUTHOR]

We develop and assess centralized and decentralized signal control systems with short-term origin-destination (OD) demands as inputs. Considering each intersection turning movement as a virtual link, we assign traffic demand to paths based on minimal instantaneous travel time. Then, the optimal control is formulated using a G/G/n/FIFO open queueing network model (QNM). We also solve the issue of optimal control using a three-step naïve method for the centralized system with the new inputs. Because the optimization of large-scale network traffic signals can involve sizeable numbers of decision variables and nonlinear constraints, making it a nondeterministic polynomial time (NP) complete problem, we further decompose the centralized system into a decentralized system where the network is divided into subnetworks. Each subnetwork has a dedicated agent that optimizes signals within it. Furthermore, traffic demand for the entire network is decomposed into demands for subnetworks via path decomposition index (PDI). The proposed control systems are applied to test scenarios constructed using different demand profiles in grid networks. We also investigate the impact of network decomposition strategy on signal control system performance. Results show that network decomposition with smaller subnetworks results in less computational time (CT) but increased average travel time (ATT) and total travel delay (TTD). [ABSTRACT FROM AUTHOR]

The elderly care station is a new concept, which is the terminal service institution of the home‐based elderly care system in Beijing. Because its supervision of service quality (SQ) is not standardized and its current subsidy is irrelevant to SQ, this paper provides a framework for an evaluation system of the elderly care station. An SQ evaluation index system for the elderly care station is designed according to the service and construction standards. A fuzzy hierarchical entropy method is then used to identify the weights such that the calculation steps are reduced and the decision‐making process is more objective. Based on that, a fuzzy comprehensive evaluation model is established. For integrating the SQ and service quantity provided by stations, a quality‐quantity quadrant model is proposed, which is used to discover the stations or operators with adequate SQ and service quantity to subsidy and the inadequate to give priority attention and rectification by quantifying and visualizing the service situation of all stations and their operators. Meanwhile, we conduct an empirical analysis by using the data of one station. [ABSTRACT FROM AUTHOR]

The major network design or data distributed problems may be described as constrained optimization problems. Constrained optimization problems include restrictions imposed by the system designers. These limitations are basically due to the system design's physical limitations or functional requirements of the network system. Constrained optimization is a computationally challenging job whenever the constraints/limitations are nonlinear and nonconvex. Furthermore, nonlinear programming methods can easily deal same optimization problem if somehow the constraints are nonlinear and convex. In this paper, we have addressed a distributed network design problem involving uncertainty that transmits data across a parallel router. This distributed network design problem is a Jackson open-type network design problem that has been formulated based on the M/M/1 queueing system. Because our network design problem is a nonlinear, convex optimization problem, we have employed a well-known Kuhn–Tucker (K-T) optimality algorithm to solve the same. Here, we have used triangular fuzzy numbers to express uncertain traffic rates and data processing rates. Then, by applying α -level interval of fuzzy numbers and their corresponding parametric representation of α -level intervals, the associated network design problem has been transformed to its parametric form and later has been solved. To obtain the optimal data stream rate in terms of interval and to illustrate the applicability of the entire approach, a hypothetical numerical example has been exhibited. Finally, the most important results have been reported. [ABSTRACT FROM AUTHOR]

In order to understand queueing performance given only partial information about the model, we propose determining intervals of likely values of performance measures given that limited information. We illustrate this approach for the mean steady-state waiting time in the $GI/GI/K$ queue. We start by specifying the first two moments of the interarrival-time and service-time distributions, and then consider additional information about these underlying distributions, in particular, a third moment and a Laplace transform value. As a theoretical basis, we apply extremal models yielding tight upper and lower bounds on the asymptotic decay rate of the steady-state waiting-time tail probability. We illustrate by constructing the theoretically justified intervals of values for the decay rate and the associated heuristically determined interval of values for the mean waiting times. Without extra information, the extremal models involve two-point distributions, which yield a wide range for the mean. Adding constraints on the third moment and a transform value produces three-point extremal distributions, which significantly reduce the range, producing practical levels of accuracy. [ABSTRACT FROM AUTHOR]

Cloud storage faces many problems in the storage process which badly affect the system's efficiency. One of the most problems is insufficient buffer space in cloud storage. This means that the packets of data wait to have storage service which may lead to weakness in performance evaluation of the system. The storage process is considered a stochastic process in which we can determine the probability distribution of the buffer occupancy and the buffer content and predict the performance behavior of the system at any time. This paper modulates a cloud storage facility as a fluid queue controlled by Markovian queue. This queue has infinite buffer capacity which determined by the M/M/1/N queue with constant arrival and service rates. We obtain the analytical solution of the distribution of the buffer occupancy. Moreover, several performance measures and numerical results are given which illustrate the effectiveness of the proposed model. [ABSTRACT FROM AUTHOR]

A closed exponential queueing G-network of unreliable multi-server nodes was studied under the asymptotic assumption of a large number of customers. The process of changing the number of functional servers in network nodes was considered as the birth--death process. The process of changing the number of customers at the nodes was considered as a continuous-state Markov process. It was proved that its probability density function satisfies the Fokker-Planck-Kolmogorov equation. The system of differential equations for the first-order and second-order moments of this process was derived. This allows us to predict the expectation, the variance and the pairwise correlation of the number of customers in the G-network nodes both in the transient and steady state. [ABSTRACT FROM AUTHOR]

We provide a queueing-theoretic framework for job replication schemes based on the principle “replicate a job as soon as the system detects it as a straggler”. This is called job speculation. Recent works have analyzed replication on arrival, which we refer to as replication. Replication is motivated by its implementation in Google’s BigTable. However, systems such as Apache Spark and Hadoop MapReduce implement speculative job execution. The performance and optimization of speculative job execution is not well understood. To this end, we propose a queueing network model for load balancing where each server can speculate on the execution time of a job. Specifically, each job is initially assigned to a single server by a frontend dispatcher. Then, when its execution begins, the server sets a timeout. If the job completes before the timeout, it leaves the network, otherwise the job is terminated and relaunched or resumed at another server where it will complete. We provide a necessary and sufficient condition for the stability of speculative queueing networks with heterogeneous servers, general job sizes and scheduling disciplines. We find that speculation can increase the stability region of the network when compared with standard load balancing models and replication schemes. We provide general conditions under which timeouts increase the size of the stability region and derive a formula for the optimal speculation time, i.e., the timeout that minimizes the load induced through speculation. We compare speculation with redundant- $d$ and redundant-to-idle-queue- $d$ rules under an $S\& X$ model. For light loaded systems, redundancy schemes provide better response times. However, for moderate to heavy loadings, redundancy schemes can lose capacity and have markedly worse response times when compared with the proposed speculative scheme. [ABSTRACT FROM AUTHOR]

Automated material handling systems play a crucial role in intelligent manufacturing workshops. The main difficulty in optimising buffer allocation in such systems is to provide good evaluation for the performance measures of interest, such as throughput, and cycle time, for customised manufacturing systems. However, existing research lacks an in-depth consideration of the integration of production and material handling systems. Therefore, a flow shop with capacitated batch transports, where the transported batch size depends on the number of jobs in buffers and capacity of transporters, is presented. The system is modelled as an open queueing network with blocking, and an approximation method is proposed for computing the performance measures. Then, an iterative optimisation algorithm embedded with the performance evaluation method is developed to determine an optimal buffer allocation. Finally, the computational experiments are conducted to validate the accuracy and efficiency of the proposed approaches. [ABSTRACT FROM AUTHOR]

The ubiquitous use of public touchscreen user interfaces for commercial applications has created a credible risk for fomite-mediated disease transmission. This paper presents results from a stochastic simulation designed to assess this risk. The model incorporates a queueing network to simulate people flow and touchscreen interactions. It also describes an updated model for microbial transmission using an asymmetric gradient transfer assumption that incorporates literature reviewed empirical data concerning touch-transfer efficiency between fingers and surfaces. In addition to natural decay/die-off, pathogens are removed from the system by simulated cleaning / disinfection and personal-touching rates (e.g. face, dermal, hair and clothing). The dose response is implemented with an exponential moving average filter to model the temporal dynamics of exposure. Public touchscreens were shown to pose a considerable infection risk (∼3%) using plausible default simulation parameters. Sensitivity of key model parameters, including the rate of surface disinfection is examined and discussed. A distinctive and important advancement of this simulation was its ability to distinguish between infection risk from a primary contaminated source and that due to the re-deposition of pathogens onto secondary, initially uncontaminated touchscreens from sequential use. The simulator is easily configurable and readily adapted to more general fomite-mediated transmission modelling and may provide a valuable framework for future research. [ABSTRACT FROM AUTHOR]

In this paper, we analyze an M/G/1 priority queueing model with finite and infinite buffers under the N , n -preemptive priority discipline, under which preemption decisions are made based on the number of high-priority customers. This priority queueing model can be used for the performance analysis of communication systems accommodating delay- and loss-sensitive packets simultaneously. To analyze the proposed model, we extend the method of delay cycle analysis and develop a queue length version of it for finite-buffer queues. Throughout our analysis, we demonstrate that by the proposed method the analysis of the complex priority queueing model can be reduced to that of simple delay cycles, so two different preemption modes of the queueing model can be dealt with in a unified way. The numerical study reveals that adjusting the decision variables N and n allows us to fine-tune system performance for different classes of customers, and N operates as a primary control variable, regardless of the preemption mode and service-time distributions. [ABSTRACT FROM AUTHOR]

Extending the results of Kruk (Queueing theory and network applications. QTNA 2019. Lecture notes in computer science, vol 11688. Springer, Cham, pp 263–275, 2019), we derive heavy traffic limit theorems for a single server, single customer class queue in which the server uses the Shortest Remaining Processing Time (SRPT) policy from heavy traffic limits for the corresponding Earliest Deadline First queueing systems. Our analysis allows for correlated customer inter-arrival and service times and heavy-tailed inter-arrival and service time distributions, as long as the corresponding stochastic primitive processes converge weakly to continuous limits under heavy traffic scaling. Our approach yields simple, concise justifications and new insights for SRPT heavy traffic limit theorems of Gromoll et al. (Stoch Syst 1(1):1–16, 2011). Corresponding results for the longest remaining processing time policy are also provided. [ABSTRACT FROM AUTHOR]

In this work, we focus on the stationary analysis of a specific class of continuous time Markov-modulated reflected random walks in the quarter plane with applications in the modelling of two-node Markov-modulated queueing networks with coupled queues. The transition rates of the two-dimensional process depend on the state of a finite state Markovian background process. Such a modulation is space homogeneous in the set of inner states of the two-dimensional lattice but may be different in the set of states at its boundaries. To obtain the stationary distribution, we apply the power series approximation method, and the theory of Riemann boundary value problems. We also obtain explicit expressions for the first moments of the stationary distribution under some symmetry assumptions. An application in the modelling of a priority retrial system with coupled orbit queues is also presented. Using a queueing network example, we numerically validated the theoretical findings. [ABSTRACT FROM AUTHOR]

The design of optical buffers for packet contention resolution has been recognized as a key issue in all-optical packet switching. One of the most general buffering schemes is priority queues, which includes first-in first-out (FIFO) queues and last-in first-out (LIFO) queues as special cases. In a priority queue, each packet is associated with a unique priority upon its arrival, the packet with the highest priority is sent out from the queue whenever there is a departure request and there are packets in the queue, and the packet with the lowest priority is dumped from the queue whenever there is a buffer overflow. In this paper, we consider the constructions of optical priority queues by using a feedback system consisting of an optical (bufferless) crossbar switch and multiple optical FIFO multiplexers with delay one (FM1’s) in the feedback path for buffering packets and feeding packets back to the switch. Such a feedback system is a generalization of that used in one of the authors’ earlier attempt for the constructions of optical priority queues in Tang et al. (2020). We fix the no-buffering problem in Tang et al. (2020) by using optical FM1’s to replace the optical FIFO multiplexers (FM’s) in Tang et al. (2020), which enables us to successfully achieve an exact emulation of a priority queue. We improve the utilization of buffering capacity over that in Tang et al. (2020) by routing packets to the optical FM1’s according to their buffering tags instead of their tags as used in Tang et al. (2020). We also extend and generalize the construction in Tang et al. (2020) and obtain a much larger class of constructions of optical priority queues. Our constructions are made possible by showing that the highest-priority (resp., lowest-priority) packet is always available at the input links of the switch whenever it needs to be routed to the departure (resp., loss) link, and by showing that there is no collision and there is no buffer overflow at any FM1 at any time so that there is no internal packet loss at any time. Our complexity analysis shows that by using a feedback system consisting of an optical $(M+2) \times (M+2)$ (bufferless) crossbar switch and $M$ fiber delay lines, we can achieve a buffer size of $2^{O(\sqrt {\alpha M})}$ , where $\alpha $ is a constant that depends on the parameters used in our constructions. Furthermore, we show that the best buffer size that we can achieve is $2^{O(\sqrt {4M/15})}$. Our result (exponential in $\sqrt {M}$) substantially improves on the best known result (polynomial in $M$) in the literature. Our numerical results show that the construction complexity of our constructions is lower than that of the construction in Tang et al. (2020), and the actual saving, in terms of the number of $2\times 2$ switches needed, by our constructions could be quite significant even in the tiny-buffer and small-buffer regimes. [ABSTRACT FROM AUTHOR]

The Markov renewal process (MRP) of M/G/1 type has been used for modeling many complex queueing systems with correlated arrivals and the special types of transitions of the MRP process corresponds to the departures from the queueing system. It can be seen from the central limit theorem for regenerative process that the distribution of the number of transitions of MRP is asymptotically normal. Thus, the asymptotic mean and variance of the number of transitions of MRP can be used to estimate the number of departures in the queueing system modelled by MRP. The aim of this paper is to present an algorithm for computing the asymptotic mean and variance for the number of level-down-transitions in a Markov renewal process of M/G/1 type with finite level. The results are applied to the queueing system with finite buffer and correlated arrivals. [ABSTRACT FROM AUTHOR]

We analyze a multi-processor two-stage tandem call center retrial queueing network in which the processors are subject to active breakdowns and repairs at stage-I. A level-dependent quasi-birth-and-death (LDQBD) process is formulated and a sufficient condition for ergodicity of the system is discussed. Under the stability condition, the stationary distribution of the number of calls in the system, the mean number of calls in the orbit, the mean waiting time of calls in the orbit and the mean busy period of the system along with other descriptors of the system are determined by using the matrix-analytic techniques. Besides, the availability analysis of the processors is also studied. Further, we have also discussed the characteristics of the first-passage time to reach the orbit critical level, the number of calls served in the call center during this period and their corresponding moments. Finally, extensive numerical results are presented to highlight the impact of the system parameters on the performance measures of the two-stage tandem call center retrial queueing system under investigation. [ABSTRACT FROM AUTHOR]