The nonpreemptive assignment of independent tasks to a system of m uniform processors isexamined with the objective of minimizing the makespan. Using r_m, the ratio of the fasest speed tothe slowest speed of the syste...The nonpreemptive assignment of independent tasks to a system of m uniform processors isexamined with the objective of minimizing the makespan. Using r_m, the ratio of the fasest speed tothe slowest speed of the system, as a parameter, we assess the performance of LPT (largestprocessing time) schedule with respect to optimal schedules. It is shown thet the worst-case boundfor the ratio of the two schedule lengths is between展开更多
In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machi...In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machine speed ratio is small or m=2. Furthermore, we present a linear compound algorithm QLC with a worst case bound of 6/5 for a two-machine system.展开更多
In multiagent systems,agents usually do not have complete information of the whole system,which makes the analysis of such systems hard.The incompleteness of information is normally modelled by means of accessibility ...In multiagent systems,agents usually do not have complete information of the whole system,which makes the analysis of such systems hard.The incompleteness of information is normally modelled by means of accessibility relations,and the schedulers consistent with such relations are called uniform.In this paper,we consider probabilistic multiagent systems with accessibility relations and focus on the model checking problem with respect to the probabilistic epistemic temporal logic,which can specify both temporal and epistemic properties.However,the problem is undecidable in general.We show that it becomes decidable when restricted to memoryless uniform schedulers.Then,we present two algorithms for this case:one reduces the model checking problem into a mixed integer non-linear programming(MINLP)problem,which can then be solved by Satisfiability Modulo Theories(SMT)solvers,and the other is an approximate algorithm based on the upper confidence bounds applied to trees(UCT)algorithm,which can return a result whenever queried.These algorithms have been implemented in an existing model checker and then validated on experiments.The experimental results show the efficiency and extendability of these algorithms,and the algorithm based on UCT outperforms the one based on MINLP in most cases.展开更多
文摘The nonpreemptive assignment of independent tasks to a system of m uniform processors isexamined with the objective of minimizing the makespan. Using r_m, the ratio of the fasest speed tothe slowest speed of the system, as a parameter, we assess the performance of LPT (largestprocessing time) schedule with respect to optimal schedules. It is shown thet the worst-case boundfor the ratio of the two schedule lengths is between
基金the National 973 Fundamental Research Project of Chinathe National Natural Sciences Foundation of China!19701028
文摘In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machine speed ratio is small or m=2. Furthermore, we present a linear compound algorithm QLC with a worst case bound of 6/5 for a two-machine system.
基金supported by the National Natural Science Foundation of China under Grant No.61836005the Australian Research Council under Grant Nos.DP220102059 and DP180100691。
文摘In multiagent systems,agents usually do not have complete information of the whole system,which makes the analysis of such systems hard.The incompleteness of information is normally modelled by means of accessibility relations,and the schedulers consistent with such relations are called uniform.In this paper,we consider probabilistic multiagent systems with accessibility relations and focus on the model checking problem with respect to the probabilistic epistemic temporal logic,which can specify both temporal and epistemic properties.However,the problem is undecidable in general.We show that it becomes decidable when restricted to memoryless uniform schedulers.Then,we present two algorithms for this case:one reduces the model checking problem into a mixed integer non-linear programming(MINLP)problem,which can then be solved by Satisfiability Modulo Theories(SMT)solvers,and the other is an approximate algorithm based on the upper confidence bounds applied to trees(UCT)algorithm,which can return a result whenever queried.These algorithms have been implemented in an existing model checker and then validated on experiments.The experimental results show the efficiency and extendability of these algorithms,and the algorithm based on UCT outperforms the one based on MINLP in most cases.
