By optimizing the network topology, this paper proposes a newmethod of queuing theory clustering algorithm based on dynamic programming in a home energy management system（ HEMS）. First, the total cost of the HEMS sy...By optimizing the network topology, this paper proposes a newmethod of queuing theory clustering algorithm based on dynamic programming in a home energy management system（ HEMS）. First, the total cost of the HEMS system is divided into two parts, the gateway installation cost and the data transmission cost. Secondly, through comparing two kinds of different queuing theories, the cost problem of the HEMS is converted into the problem of gateway deployment. Finally, a machine-to-machine（ M2M） gateway configuration scheme is designed to minimize the cost of the system. Simulation results showthat the cost of the HEMS system mainly comes from the installation cost of the gateways when the gateway buffer space is large enough. If the gateway buffer space is limited, the proposed queue algorithm can effectively achieve optimal gateway setting while maintaining the minimal cost of the HEMS at desired levels through marginal analyses and the properties of cost minimization.展开更多
This paper deals with a type of servicing machines model, which service station has a life time of the kth Er-langian distribution and can be repaired just like a new one. The cyclic time and the inefficiency quantiti...This paper deals with a type of servicing machines model, which service station has a life time of the kth Er-langian distribution and can be repaired just like a new one. The cyclic time and the inefficiency quantities of this system in equilibrium are obtained.展开更多
The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their ...The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their earlier tasks and may join with tasks from other programs. This phenomenon is called exchangeable join (EJ), which introduces correlation to the task’s service time. In this work, we investigate the response time of multiprocessor systems with EJ with a new approach. We analyze two aspects of this kind of systems: exchangeable join (EJ) and the capacity constraint (CC). We prove that the system response time can be effectively reduced by EJ, while the reduced amount is constrained by the capacity of the multiprocessor. An upper bound model is constructed based on this analysis and a quick estimation algorithm is proposed. The approximation formula is verified by extensive simulation results, which show that the relative error of approximation is less than 5%.展开更多
An appointment scheduling problem is studied with the consideration of customer impatience.On the assumption that both the time of leaving queue and the time of service are exponentially distributed,in order to minimi...An appointment scheduling problem is studied with the consideration of customer impatience.On the assumption that both the time of leaving queue and the time of service are exponentially distributed,in order to minimize the joint cost,the optimal appointment schedule of the fixed number of customers is studied.The joint cost function is composed of customers expected delay time and service availability time.The expected delay time of each customer in the queue is recursively computed in terms of customer interarrival time.Furthermore,the effect of impatience on the optimal schedule as well as the total operating cost is studied.The results show that as the impatience rate increases,the optimal interarrival time becomes shorter and the interarrival time of the last few customers gradually approaches that of the customers in the middle.In addition,impatient behaviors can increase the joint cost.展开更多
One of the fundamental problems in parallel and distributed systems is deciding how to allocate jobs to processors. The goals of job scheduling in a parallel environment are to minimize the parallel execution time of ...One of the fundamental problems in parallel and distributed systems is deciding how to allocate jobs to processors. The goals of job scheduling in a parallel environment are to minimize the parallel execution time of a job and try to balance the user’s desire with the system’s desire. The users always want their jobs be completed as quickly as possible, while the system wants to service as many jobs as possible. In this paper, a dynamic job scheduling algorithm was introduced. This algorithm tries to utilize the information of a practical system to allocate the jobs more evenly. The communication time between the processor and scheduler is overlapped with the computation time of the processor. So the communication overhead can be little. The principle of scheduling the job is based on the desirability of each processor. The scheduler would not allocate a new job to a processor that is already fully utilized. The execution efficiency of the system will be increased. This algorithm also can be reused in other complex algorithms.展开更多
Based on the queuing theory, a nonlinear optimization model is proposed in this paper. A novel transformation of optimization variables is devised and the constraints are properly combined so as to make this model int...Based on the queuing theory, a nonlinear optimization model is proposed in this paper. A novel transformation of optimization variables is devised and the constraints are properly combined so as to make this model into a convex one, from which the Lagrangian function and the KKT conditions are derived. The interiorpoint method for convex optimization is presented here as a computationally efficient tool. Finally, this model is evaluated on a real example, from which such conclusions are drawn that the optimum result can ensure the full utilization of machines and the least amount of WIP in manufacturing systems; the interior-point method for convex optimization needs fewer iterations with significant computational savings. It appears that many non-linear ootimization oroblems in the industrial engineering field would be amenable to this method of solution.展开更多
The IP P＋M/M/c queueing system has been extensively used in the modern communication system.The existence and uniqueness of stationary distribution of the queue length L（t）for IP P＋M/M/1 queue has been proved in[1...The IP P＋M/M/c queueing system has been extensively used in the modern communication system.The existence and uniqueness of stationary distribution of the queue length L（t）for IP P＋M/M/1 queue has been proved in[10].In this paper,we shall give the su？cient and necessary conditions of l-ergodicity,geometric ergodicity,and prove that they are neither uniformly polynomial ergodicity nor strong ergodicity.展开更多
For an ergodic continuous-time Markov process with a particular state in its space,the authors provide the necessary and sufficient conditions for exponential and strong ergodicity in terms of the moments of the first...For an ergodic continuous-time Markov process with a particular state in its space,the authors provide the necessary and sufficient conditions for exponential and strong ergodicity in terms of the moments of the first hitting time on the state.An application to the queue length process of M/G/1 queue with multiple vacations is given.展开更多
On the basic of a type of practical examples we set up a new queueing model with negative customers. By the use of “Supplemental Variables method” and “State transfer analysis”, we get the generating function wit...On the basic of a type of practical examples we set up a new queueing model with negative customers. By the use of “Supplemental Variables method” and “State transfer analysis”, we get the generating function with negative powers of queue length and the waiting time expressions.展开更多
We consider the problem of scheduling n jobs in a pallet-constrained flow shop so as to minimize the makespan.In such a flow shop environment,each job needs a pallet the entire time,from the start of its first operati...We consider the problem of scheduling n jobs in a pallet-constrained flow shop so as to minimize the makespan.In such a flow shop environment,each job needs a pallet the entire time,from the start of its first operation until the completion of the last operation,and the number of pallets in the shop at any given time is limited by a positive integer,K≤n.Generally speaking,the optimal schedules may be passing schedules.In this paper,we present a combinatorial property which shows that for two machines,K(K≥3）pallets,there exists a no-passing schedule which is an optimal schedule for n≤2K-1 and 2K-1 is tight.展开更多
This paper considers the completion time and the interruption time of a job processed on an unreliable machine. By using the general theory of stochastic orderings, we obtain the closure properties of the distribution...This paper considers the completion time and the interruption time of a job processed on an unreliable machine. By using the general theory of stochastic orderings, we obtain the closure properties of the distribution of the completion time and the interruption time on L^+ and PH life distribution classes. We get an exponential bound for the tail probability of the interruption time.展开更多
基金The National Natural Science Foundation of China(No.61471031)the Fundamental Research Funds for the Central Universities(No.2013JBZ01)the Program for New Century Excellent Talents in University of Ministry of Education of China(No.NCET-12-0766)
文摘By optimizing the network topology, this paper proposes a newmethod of queuing theory clustering algorithm based on dynamic programming in a home energy management system（ HEMS）. First, the total cost of the HEMS system is divided into two parts, the gateway installation cost and the data transmission cost. Secondly, through comparing two kinds of different queuing theories, the cost problem of the HEMS is converted into the problem of gateway deployment. Finally, a machine-to-machine（ M2M） gateway configuration scheme is designed to minimize the cost of the system. Simulation results showthat the cost of the HEMS system mainly comes from the installation cost of the gateways when the gateway buffer space is large enough. If the gateway buffer space is limited, the proposed queue algorithm can effectively achieve optimal gateway setting while maintaining the minimal cost of the HEMS at desired levels through marginal analyses and the properties of cost minimization.
文摘This paper deals with a type of servicing machines model, which service station has a life time of the kth Er-langian distribution and can be repaired just like a new one. The cyclic time and the inefficiency quantities of this system in equilibrium are obtained.
基金Project supported by the National Natural Science Foundation of0 China (Nos. 60274011 and 60574067), and the Program for NewCentury Excellent Talents in University (No. NCET-04-0094), China
文摘The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their earlier tasks and may join with tasks from other programs. This phenomenon is called exchangeable join (EJ), which introduces correlation to the task’s service time. In this work, we investigate the response time of multiprocessor systems with EJ with a new approach. We analyze two aspects of this kind of systems: exchangeable join (EJ) and the capacity constraint (CC). We prove that the system response time can be effectively reduced by EJ, while the reduced amount is constrained by the capacity of the multiprocessor. An upper bound model is constructed based on this analysis and a quick estimation algorithm is proposed. The approximation formula is verified by extensive simulation results, which show that the relative error of approximation is less than 5%.
基金The National Natural Science Foundation of China(No.71671036)the Scientific Innovation Research of Graduate Students in Jiangsu Province(No.KYLX_0211)
文摘An appointment scheduling problem is studied with the consideration of customer impatience.On the assumption that both the time of leaving queue and the time of service are exponentially distributed,in order to minimize the joint cost,the optimal appointment schedule of the fixed number of customers is studied.The joint cost function is composed of customers expected delay time and service availability time.The expected delay time of each customer in the queue is recursively computed in terms of customer interarrival time.Furthermore,the effect of impatience on the optimal schedule as well as the total operating cost is studied.The results show that as the impatience rate increases,the optimal interarrival time becomes shorter and the interarrival time of the last few customers gradually approaches that of the customers in the middle.In addition,impatient behaviors can increase the joint cost.
基金National Natural Science Foundation of China( No.60 173 0 3 1)
文摘One of the fundamental problems in parallel and distributed systems is deciding how to allocate jobs to processors. The goals of job scheduling in a parallel environment are to minimize the parallel execution time of a job and try to balance the user’s desire with the system’s desire. The users always want their jobs be completed as quickly as possible, while the system wants to service as many jobs as possible. In this paper, a dynamic job scheduling algorithm was introduced. This algorithm tries to utilize the information of a practical system to allocate the jobs more evenly. The communication time between the processor and scheduler is overlapped with the computation time of the processor. So the communication overhead can be little. The principle of scheduling the job is based on the desirability of each processor. The scheduler would not allocate a new job to a processor that is already fully utilized. The execution efficiency of the system will be increased. This algorithm also can be reused in other complex algorithms.
文摘Based on the queuing theory, a nonlinear optimization model is proposed in this paper. A novel transformation of optimization variables is devised and the constraints are properly combined so as to make this model into a convex one, from which the Lagrangian function and the KKT conditions are derived. The interiorpoint method for convex optimization is presented here as a computationally efficient tool. Finally, this model is evaluated on a real example, from which such conclusions are drawn that the optimum result can ensure the full utilization of machines and the least amount of WIP in manufacturing systems; the interior-point method for convex optimization needs fewer iterations with significant computational savings. It appears that many non-linear ootimization oroblems in the industrial engineering field would be amenable to this method of solution.
基金Supported by the Chinese Universities Scientific Fund(BUPT2009RC0707,BUPT2011RC0703)
文摘The IP P＋M/M/c queueing system has been extensively used in the modern communication system.The existence and uniqueness of stationary distribution of the queue length L（t）for IP P＋M/M/1 queue has been proved in[10].In this paper,we shall give the su？cient and necessary conditions of l-ergodicity,geometric ergodicity,and prove that they are neither uniformly polynomial ergodicity nor strong ergodicity.
基金the National Natural Science Foundation of China(No.10671212)the Research Fund for the Doctoral Program of Higher Education(No.20050533036).
文摘For an ergodic continuous-time Markov process with a particular state in its space,the authors provide the necessary and sufficient conditions for exponential and strong ergodicity in terms of the moments of the first hitting time on the state.An application to the queue length process of M/G/1 queue with multiple vacations is given.
基金This research is supported by the the Scientific Foundation of Jiangsu Province (BK97047) and the Foundation of Jiangsu Education bureau (00KJT11003)
文摘On the basic of a type of practical examples we set up a new queueing model with negative customers. By the use of “Supplemental Variables method” and “State transfer analysis”, we get the generating function with negative powers of queue length and the waiting time expressions.
基金This author is supported by Netherlands organization for international cooperation in high education.
文摘We consider the problem of scheduling n jobs in a pallet-constrained flow shop so as to minimize the makespan.In such a flow shop environment,each job needs a pallet the entire time,from the start of its first operation until the completion of the last operation,and the number of pallets in the shop at any given time is limited by a positive integer,K≤n.Generally speaking,the optimal schedules may be passing schedules.In this paper,we present a combinatorial property which shows that for two machines,K(K≥3）pallets,there exists a no-passing schedule which is an optimal schedule for n≤2K-1 and 2K-1 is tight.
基金This work is partially supported by the National Natural Science Foundation of China(Grant No. 60074018,No. 10271102)the Natural Science Foundation of Hebei Province(Grant No. A2004000185)and the Doctoral Foundation of Hebei Province(Grant No. 2002131).
文摘This paper considers the completion time and the interruption time of a job processed on an unreliable machine. By using the general theory of stochastic orderings, we obtain the closure properties of the distribution of the completion time and the interruption time on L^+ and PH life distribution classes. We get an exponential bound for the tail probability of the interruption time.
