文献类型：期刊文献

英文题名：Vehicle scheduling problems with two agents on a line

作者：Yan, Hao[1];Liu, Peihai[1];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Shanghai, Peoples R China

年份：2023

卷号：45

期号：1

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：;EI(收录号：20224713146356);WOS:【SCI-EXPANDED(收录号:WOS:000886136700001)】；

基金：This research was supported by the National Natural Science Foundation of China under Grant 11871213.

语种：英文

外文关键词：Network scheduling; Agent scheduling; Polynomial time algorithm; Approximation algorithm

摘要：This paper studies the two-agent vehicle scheduling problems on a line with the constraint that each job is processed after its release time. All jobs belong to agent A or agent B and each job is located at some vertex on the line. The vehicle starts from an initial vertex vo to process all jobs. The objective of the problem is to find a route of the vehicle so as to minimize the makespan of agent A under the constraint condition that the makespan of agent B is no more than the threshold value Q. This problem can be expressed by the 3-field scheduling notations as line - l vertical bar r(v(j)), C-max(B) <= Q vertical bar C-max(A), For the problem without release time, we show this problem is solvable in polynomial time and an O(n) time algorithm is provided. For the problem with release time, we prove this problem is NP-hard and then, a 3+root 5/2-approximation algorithm is presented. Finally, we conclude the numerical experiments to evaluate the performance of the approximation algorithm.