文献类型：期刊文献

英文题名：TWO-AGENT VEHICLE SCHEDULING PROBLEM ON A LINE-SHAPED NETWORK

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

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

年份：2023

卷号：19

期号：7

起止页码：4874

外文期刊名：JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION

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

基金：The third author is supported by the National Natural Science Foundation of China under Grant 11871213.

语种：英文

外文关键词：Agent scheduling; network scheduling; complexity; polynomial time algorithm; approximation algorithm

摘要：This paper studies single vehicle scheduling problems with two agents on a line-shaped network. Each of two agents has some customers that are situated at some vertices on the network. A vehicle has to start from upsilon(0) to serve all customers. The objective is to schedule the customers to minimize C-max(A) + theta C-max(B), where C-max(X) is the latest completion time of the customers for agent X and X is an element of{A,B}. We first propose a polynomial time algorithm for the problem without release time. Next, the problem with release time is proved to be NP-hard despite of a network with only two vertices. Then, we present a 3+root 5/2 -approximation algorithm. Finally, numerical experiments are carried out to verify the approximation algorithm is effective.