Vehicle scheduling problems with two agents on a line

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.