Vehicle scheduling problems with two agents on a line

Hao Yan (), Peihai Liu () and Xiwen Lu ()
Additional contact information
Hao Yan: East China University of Science and Technology
Peihai Liu: East China University of Science and Technology
Xiwen Lu: East China University of Science and Technology

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 7, 18 pages

Abstract: Abstract 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 $$v_{0}$$ v 0 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-1|r(v_{j}),~C_{max}^{B}\le Q|C_{max}^{A}$$ l i n e - 1 | r ( v j ) , C max B ≤ Q | 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 $$\frac{3+\sqrt{5}}{2}$$ 3 + 5 2 -approximation algorithm is presented. Finally, we conclude the numerical experiments to evaluate the performance of the approximation algorithm.

Keywords: Network scheduling; Agent scheduling; Polynomial time algorithm; Approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00933-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00933-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00933-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().