People often have to queue for a busy service in many places around a city, and knowing the queue time can be helpful for making better activity plans to avoid long queues. Traditional solutions to the queue time moni...People often have to queue for a busy service in many places around a city, and knowing the queue time can be helpful for making better activity plans to avoid long queues. Traditional solutions to the queue time monitoring are based on pre-deployed infrastructures, such as cameras and infrared sensors, which are costly and fail to deliver the queue time information to scattered citizens. This paper presents CrowdQTE, a mobile crowdsensing system, which utilizes the sensor-enhanced mobile devices and crowd hu- man intelligence to monitor and provide real-time queue time information for various queuing scenarios. When people are waiting in a line, we utilize the accelerometer sensor data and ambient contexts to automatically detect the queueing behav- ior and calculate the queue time. When people are not waiting in a line, it estimates the queue time based on the information reported manually by participants. We evaluate the perfor- mance of the system with a two-week and 12-person deploy- ment using commercially-available smartphones. The results demonstrate that CrowdQTE is effective in estimating queu- ing status.展开更多
We consider a discrete-time multi-server finite-capacity queueing system with correlated batch arrivals and deterministic service times (of single slot), which has a variety of potential applications in slotted digita...We consider a discrete-time multi-server finite-capacity queueing system with correlated batch arrivals and deterministic service times (of single slot), which has a variety of potential applications in slotted digital telecommunication systems and other related areas. For this queueing system, we present, based on Markov chain analysis, not only the steady-state distributions but also the transient distributions of the system length and of the system waiting time in a simple and unified manner. From these distributions, important performance measures of practical interest can be easily obtained. Numerical examples concerning the superposition of certain video traffics are presented at the end.展开更多
In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the...In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting time Wk(t) at time t of class k is derived by the method of collective marks. A sufficient condition for , where U has the standard normal distribution, is also given.展开更多
It is well known, in queueing theory, that the system performance is greatly influenced by scheduling policy. No universal optimum scheduling strategy exists in systems where individual customer service demands are no...It is well known, in queueing theory, that the system performance is greatly influenced by scheduling policy. No universal optimum scheduling strategy exists in systems where individual customer service demands are not known a priori. However, if the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. Our particular research contribution is in exploring the use of this function to enhance system performance by increasing the probability that a job will meet its deadline. In a detailed discrete event simulation, we have tested many different distributions with a wide range of C2 and shapes, as well as for single and dual processor system. Results of four distributions are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. In the study of the use of two slow servers versus one fast server, we have discovered that they provide comparable performance, and in a few cases the double server system does better.展开更多
Formation and scheduling are the most important decisions in the virtual modular manufacturing system;however,the global performance optimization of the system may be sacrificed via the superposition of two independen...Formation and scheduling are the most important decisions in the virtual modular manufacturing system;however,the global performance optimization of the system may be sacrificed via the superposition of two independent decision-making results.The joint decision of formation and scheduling is very important for system design.Complex and discrete manufacturing enterprises such as shipbuilding and aerospace often comprise multiple tasks,processes,and parallel machines,resulting in complex routes.The queuing time of parts in front of machines may account for 90%of the production cycle time.This study established a weighted allocation model of a formation-scheduling joint decision problem considering queuing time in system.To solve this nondeterministic polynomial(NP)problem,an adaptive differential evolution-simulated annealing(ADE-SA)algorithm is proposed.Compared with the standard differential evolution(DE)algorithm,the adaptive mutation factor overcomes the disadvantage that the scale of DE’s differential vector is difficult to control.The selection strategy of the SA algorithm compensates for the deficiency that DE’s greedy strategy may fall into a local optimal solution.The comparison results of four algorithms of a series of random examples demonstrate that the overall performance of ADE-SA is superior to the genetic algorithm,and average iteration,maximum completion time,and move time are 24%,11%,and 7%lower than the average of other three algorithms,respectively.The method can generate the joint decision-making scheme with better overall performance,and effectively identify production bottlenecks through quantitative analysis of queuing time.展开更多
In this paper, the Geometry/G/1 queueing model with inter-arrival times generated by a geometric（parameter p） distribution according to a late arrival system with delayed access and service times independently distr...In this paper, the Geometry/G/1 queueing model with inter-arrival times generated by a geometric（parameter p） distribution according to a late arrival system with delayed access and service times independently distributed with distribution {gj }, j≥ 1 is studied. By a simple method （techniques of probability decomposition, renewal process theory） that is different from the techniques used by Hunter（1983）, the transient property of the queue with initial state i（i ≥ 0） is discussed. The recursion expression for u -transform of transient queue-length distribution at any time point n^＋ is obtained, and the recursion expression of the limiting queue length distribution is also obtained.展开更多
In the era of Big Data, typical architecture of distributed real-time stream processing systems is the combination of Flume, Kafka, and Storm. As a kind of distributed message system, Kafka has the characteristics of ...In the era of Big Data, typical architecture of distributed real-time stream processing systems is the combination of Flume, Kafka, and Storm. As a kind of distributed message system, Kafka has the characteristics of horizontal scalability and high throughput, which is manly deployed in many areas in order to address the problem of speed mismatch between message producers and consumers. When using Kafka, we need to quickly receive data sent by producers. In addition, we need to send data to consumers quickly. Therefore, the performance of Kafka is of critical importance to the performance of the whole stream processing system. In this paper, we propose the improved design of real-time stream processing systems, and focus on improving the Kafka's data loading process.We use Kafka cat to transfer data from the source to Kafka topic directly, which can reduce the network transmission. We also utilize the memory file system to accelerate the process of data loading, which can address the bottleneck and performance problems caused by disk I/O. Extensive experiments are conducted to evaluate the performance, which show the superiority of our improved design.展开更多
Long departure-taxi-out time leads to significant airport surface congestion, fuel-burn costs, and excessive emissions of greenhouse gases. To reduce these undesirable effects, a Predicted taxi-out time-based Dynamic ...Long departure-taxi-out time leads to significant airport surface congestion, fuel-burn costs, and excessive emissions of greenhouse gases. To reduce these undesirable effects, a Predicted taxi-out time-based Dynamic Pushback Control(PDPC) method is proposed. The implementation of this method requires two steps: first, the taxi-out times for aircraft are predicted by the leastsquares support-vector regression approach of which the parameters are optimized by an introduced improved Firefly algorithm. Then, a dynamic pushback control model equipped with a linear gate-hold penalty function is built, along with a proposed iterative taxiway queue-threshold optimization algorithm for solving the model. A case study with data obtained from Beijing International airport(PEK) is presented. The taxi-out time prediction model achieves predictive accuracy within 3 min and 5 min by 84.71% and 95.66%, respectively. The results of the proposed pushback method show that total operation cost and fuel-burn cost achieve a 14.0% and 21.1%reduction, respectively, as compared to the traditional K-control policy.(3) From the perspective of implementation, using PDPC policy can significantly reduce the queue length in taxiway and taxi-out time. The total operation cost and fuel-burn cost can be curtailed by 37.2% and 52.1%,respectively, as compared to the non-enforcement of any pushback control mechanism. These results show that the proposed pushback control model can reduce fuel-burn costs and airport surface congestion effectively.展开更多
This paper considers a Geo/Geo/1 queueing system with infinite capacity, in which the service rate changes depending on the workload. Initially, when the number of customers in the system is less than a certain thresh...This paper considers a Geo/Geo/1 queueing system with infinite capacity, in which the service rate changes depending on the workload. Initially, when the number of customers in the system is less than a certain threshold L, low service rate is provided for cost saving. On the other hand, the high service rate is activated as soon as L customers accumulate in the system and such service rate is preserved until the system becomes completely empty even if the number of customers falls below L. The steady-state probability distribution and the expected number of customers in the system are derived. Through the first-step argument, a recursive algorithm for computing the first moment of the conditional sojourn time is obtained. Furthermore, employing the results of regeneration cycle analysis, the direct search method is also implemented to determine the optimal value of L for minimizing the long-run average cost rate function.展开更多
We consider a real time data acquisition and processing multiserver system with identical servers (such as unmanned aerial vehicles, machine controllers, overhearing devices, medical monitoring devices, etc.) which ca...We consider a real time data acquisition and processing multiserver system with identical servers (such as unmanned aerial vehicles, machine controllers, overhearing devices, medical monitoring devices, etc.) which can be maintained/programmed for different kinds of activities (e.g. passive or active). This system provides a service for real time tasks arriving via several channels (such as surveillance regions, assembly lines, communication channels, etc.) and involves maintenance. We focus on the worst case analysis of the system with ample maintenance facilities exponentially distributed time to failure and maintenance times. We consider two kinds of models (with and without nonpreemptive priorities) and provide balance equations for steady state probabilities and various performance measures, when both operation and maintenance times are exponentially distributed.展开更多
We study a batch arrival MX/M/1 queue with multiple working vacation. The server serves customers at a lower rate rather than completely stopping service during the service period. Using a quasi upper triangular trans...We study a batch arrival MX/M/1 queue with multiple working vacation. The server serves customers at a lower rate rather than completely stopping service during the service period. Using a quasi upper triangular transition probability matrix of two-dimensional Markov chain and matrix analytic method, the probability generating function (PGF) of the stationary system length distribution is obtained, from which we obtain the stochastic decomposition structure of system length which indicates the relationship with that of the MX/M/1 queue without vacation. Some performance indices are derived by using the PGF of the stationary system length distribution. It is important that we obtain the Laplace Stieltjes transform (LST) of the stationary waiting time distribution. Further, we obtain the mean system length and the mean waiting time. Finally, numerical results for some special cases are presented to show the effects of system parameters.展开更多
In this paper, we study a single server queueing system with Coxian-2 service. In Particular, we study M/C-2/M/1 queue with Coxian-2 service and exponential vacation. We assume that units (customers) arrive at t...In this paper, we study a single server queueing system with Coxian-2 service. In Particular, we study M/C-2/M/1 queue with Coxian-2 service and exponential vacation. We assume that units (customers) arrive at the system one by one in a Poisson process and the server provides one-by-one service based on first in first out (FIFO) rule. We obtained the steady state queue size distributions in terms of the probability generating functions, the average number of customers and their average waiting time in the system as well as in the queue.展开更多
Weighted priority queueing is a modification of priority queueing that eliminates the possibility of blocking lower priority traffic. The weights assigned to priority classes determine the fractions of the bandwith th...Weighted priority queueing is a modification of priority queueing that eliminates the possibility of blocking lower priority traffic. The weights assigned to priority classes determine the fractions of the bandwith that are guaranteed for individual traffic classes, similarly as in weighted fair queueing. The paper describes a timed Petri net model of weighted priority queueing and uses discrete-event simulation of this model to obtain performance characteristics of simple queueing systems. The model is also used to analyze the effects of finite queue capacity on the performance of queueing systems.展开更多
基金This work was mainly funded by the National Natural Science Foundation of China （Grant No. 61572048）, Research Fund from China Electric Power Research Institute （JS71-16-005）, and Microsoft Col- laboration Research Grant. Besides, the work was partially supported by the Fundamental Research Funds for the Central Universities （106112015CD-JXY180001）, Open Research Fund Program of Shenzhen Key Laboratory of Spatial Smart Sensing and Services （Shenzhen University, China）, and Chongqing Basic and Frontier Research Program （cstc2015jcyjA00016）.
文摘People often have to queue for a busy service in many places around a city, and knowing the queue time can be helpful for making better activity plans to avoid long queues. Traditional solutions to the queue time monitoring are based on pre-deployed infrastructures, such as cameras and infrared sensors, which are costly and fail to deliver the queue time information to scattered citizens. This paper presents CrowdQTE, a mobile crowdsensing system, which utilizes the sensor-enhanced mobile devices and crowd hu- man intelligence to monitor and provide real-time queue time information for various queuing scenarios. When people are waiting in a line, we utilize the accelerometer sensor data and ambient contexts to automatically detect the queueing behav- ior and calculate the queue time. When people are not waiting in a line, it estimates the queue time based on the information reported manually by participants. We evaluate the perfor- mance of the system with a two-week and 12-person deploy- ment using commercially-available smartphones. The results demonstrate that CrowdQTE is effective in estimating queu- ing status.
文摘We consider a discrete-time multi-server finite-capacity queueing system with correlated batch arrivals and deterministic service times (of single slot), which has a variety of potential applications in slotted digital telecommunication systems and other related areas. For this queueing system, we present, based on Markov chain analysis, not only the steady-state distributions but also the transient distributions of the system length and of the system waiting time in a simple and unified manner. From these distributions, important performance measures of practical interest can be easily obtained. Numerical examples concerning the superposition of certain video traffics are presented at the end.
文摘In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting time Wk(t) at time t of class k is derived by the method of collective marks. A sufficient condition for , where U has the standard normal distribution, is also given.
文摘It is well known, in queueing theory, that the system performance is greatly influenced by scheduling policy. No universal optimum scheduling strategy exists in systems where individual customer service demands are not known a priori. However, if the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. Our particular research contribution is in exploring the use of this function to enhance system performance by increasing the probability that a job will meet its deadline. In a detailed discrete event simulation, we have tested many different distributions with a wide range of C2 and shapes, as well as for single and dual processor system. Results of four distributions are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. In the study of the use of two slow servers versus one fast server, we have discovered that they provide comparable performance, and in a few cases the double server system does better.
基金supported by the National Natural Science Foundation of China(Grant No.:71972090).
文摘Formation and scheduling are the most important decisions in the virtual modular manufacturing system;however,the global performance optimization of the system may be sacrificed via the superposition of two independent decision-making results.The joint decision of formation and scheduling is very important for system design.Complex and discrete manufacturing enterprises such as shipbuilding and aerospace often comprise multiple tasks,processes,and parallel machines,resulting in complex routes.The queuing time of parts in front of machines may account for 90%of the production cycle time.This study established a weighted allocation model of a formation-scheduling joint decision problem considering queuing time in system.To solve this nondeterministic polynomial(NP)problem,an adaptive differential evolution-simulated annealing(ADE-SA)algorithm is proposed.Compared with the standard differential evolution(DE)algorithm,the adaptive mutation factor overcomes the disadvantage that the scale of DE’s differential vector is difficult to control.The selection strategy of the SA algorithm compensates for the deficiency that DE’s greedy strategy may fall into a local optimal solution.The comparison results of four algorithms of a series of random examples demonstrate that the overall performance of ADE-SA is superior to the genetic algorithm,and average iteration,maximum completion time,and move time are 24%,11%,and 7%lower than the average of other three algorithms,respectively.The method can generate the joint decision-making scheme with better overall performance,and effectively identify production bottlenecks through quantitative analysis of queuing time.
基金This work was supported by the Scientific Research Fund of Southwestern University of Finance and Economics and the Science Foundation of Sichuan Normal University.
文摘In this paper, the Geometry/G/1 queueing model with inter-arrival times generated by a geometric（parameter p） distribution according to a late arrival system with delayed access and service times independently distributed with distribution {gj }, j≥ 1 is studied. By a simple method （techniques of probability decomposition, renewal process theory） that is different from the techniques used by Hunter（1983）, the transient property of the queue with initial state i（i ≥ 0） is discussed. The recursion expression for u -transform of transient queue-length distribution at any time point n^＋ is obtained, and the recursion expression of the limiting queue length distribution is also obtained.
基金supported by the Research Fund of National Key Laboratory of Computer Architecture under Grant No.CARCH201501the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing under Grant No.2016A09
文摘In the era of Big Data, typical architecture of distributed real-time stream processing systems is the combination of Flume, Kafka, and Storm. As a kind of distributed message system, Kafka has the characteristics of horizontal scalability and high throughput, which is manly deployed in many areas in order to address the problem of speed mismatch between message producers and consumers. When using Kafka, we need to quickly receive data sent by producers. In addition, we need to send data to consumers quickly. Therefore, the performance of Kafka is of critical importance to the performance of the whole stream processing system. In this paper, we propose the improved design of real-time stream processing systems, and focus on improving the Kafka's data loading process.We use Kafka cat to transfer data from the source to Kafka topic directly, which can reduce the network transmission. We also utilize the memory file system to accelerate the process of data loading, which can address the bottleneck and performance problems caused by disk I/O. Extensive experiments are conducted to evaluate the performance, which show the superiority of our improved design.
基金partially supported by the National Natural Science Foundation of China-Civil Aviation Joint Fund(Nos.U1533203,U1233124.)
文摘Long departure-taxi-out time leads to significant airport surface congestion, fuel-burn costs, and excessive emissions of greenhouse gases. To reduce these undesirable effects, a Predicted taxi-out time-based Dynamic Pushback Control(PDPC) method is proposed. The implementation of this method requires two steps: first, the taxi-out times for aircraft are predicted by the leastsquares support-vector regression approach of which the parameters are optimized by an introduced improved Firefly algorithm. Then, a dynamic pushback control model equipped with a linear gate-hold penalty function is built, along with a proposed iterative taxiway queue-threshold optimization algorithm for solving the model. A case study with data obtained from Beijing International airport(PEK) is presented. The taxi-out time prediction model achieves predictive accuracy within 3 min and 5 min by 84.71% and 95.66%, respectively. The results of the proposed pushback method show that total operation cost and fuel-burn cost achieve a 14.0% and 21.1%reduction, respectively, as compared to the traditional K-control policy.(3) From the perspective of implementation, using PDPC policy can significantly reduce the queue length in taxiway and taxi-out time. The total operation cost and fuel-burn cost can be curtailed by 37.2% and 52.1%,respectively, as compared to the non-enforcement of any pushback control mechanism. These results show that the proposed pushback control model can reduce fuel-burn costs and airport surface congestion effectively.
文摘This paper considers a Geo/Geo/1 queueing system with infinite capacity, in which the service rate changes depending on the workload. Initially, when the number of customers in the system is less than a certain threshold L, low service rate is provided for cost saving. On the other hand, the high service rate is activated as soon as L customers accumulate in the system and such service rate is preserved until the system becomes completely empty even if the number of customers falls below L. The steady-state probability distribution and the expected number of customers in the system are derived. Through the first-step argument, a recursive algorithm for computing the first moment of the conditional sojourn time is obtained. Furthermore, employing the results of regeneration cycle analysis, the direct search method is also implemented to determine the optimal value of L for minimizing the long-run average cost rate function.
文摘We consider a real time data acquisition and processing multiserver system with identical servers (such as unmanned aerial vehicles, machine controllers, overhearing devices, medical monitoring devices, etc.) which can be maintained/programmed for different kinds of activities (e.g. passive or active). This system provides a service for real time tasks arriving via several channels (such as surveillance regions, assembly lines, communication channels, etc.) and involves maintenance. We focus on the worst case analysis of the system with ample maintenance facilities exponentially distributed time to failure and maintenance times. We consider two kinds of models (with and without nonpreemptive priorities) and provide balance equations for steady state probabilities and various performance measures, when both operation and maintenance times are exponentially distributed.
文摘We study a batch arrival MX/M/1 queue with multiple working vacation. The server serves customers at a lower rate rather than completely stopping service during the service period. Using a quasi upper triangular transition probability matrix of two-dimensional Markov chain and matrix analytic method, the probability generating function (PGF) of the stationary system length distribution is obtained, from which we obtain the stochastic decomposition structure of system length which indicates the relationship with that of the MX/M/1 queue without vacation. Some performance indices are derived by using the PGF of the stationary system length distribution. It is important that we obtain the Laplace Stieltjes transform (LST) of the stationary waiting time distribution. Further, we obtain the mean system length and the mean waiting time. Finally, numerical results for some special cases are presented to show the effects of system parameters.
文摘In this paper, we study a single server queueing system with Coxian-2 service. In Particular, we study M/C-2/M/1 queue with Coxian-2 service and exponential vacation. We assume that units (customers) arrive at the system one by one in a Poisson process and the server provides one-by-one service based on first in first out (FIFO) rule. We obtained the steady state queue size distributions in terms of the probability generating functions, the average number of customers and their average waiting time in the system as well as in the queue.
文摘Weighted priority queueing is a modification of priority queueing that eliminates the possibility of blocking lower priority traffic. The weights assigned to priority classes determine the fractions of the bandwith that are guaranteed for individual traffic classes, similarly as in weighted fair queueing. The paper describes a timed Petri net model of weighted priority queueing and uses discrete-event simulation of this model to obtain performance characteristics of simple queueing systems. The model is also used to analyze the effects of finite queue capacity on the performance of queueing systems.
