A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a sourc...A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.展开更多
This paper studies the two-agent scheduling on a bounded parallel-batching machine.In the problem,there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of a...This paper studies the two-agent scheduling on a bounded parallel-batching machine.In the problem,there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of agent B are equal.The jobs of different agents can be processed in a common batch.Moreover,each agent has its own objective function to be minimized.The objective function of agent A is the makespan of its jobs,and the objective function of agent B is the maximum lateness of its jobs.We present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.展开更多
基金Supported by the National Natural Science Foundation of China(No.10531070,No.10771209,No.10721101)Chinese Academy of Sciences under Grant No.kjcx-yw-s7
文摘A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.
基金This research was supported in part by the National Natural Science Foundation of China(Nos.11401604,11571323,11701595,11501279)also supported by Program for Interdisciplinary Direction Team in Zhongyuan University of Technology,China.
文摘This paper studies the two-agent scheduling on a bounded parallel-batching machine.In the problem,there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of agent B are equal.The jobs of different agents can be processed in a common batch.Moreover,each agent has its own objective function to be minimized.The objective function of agent A is the makespan of its jobs,and the objective function of agent B is the maximum lateness of its jobs.We present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.
