×

2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. (English) Zbl 1034.68122

Summary: Given a path \(G\) with \(n\) vertices \(v_1,v_2,\dots,v_n\) and \(m\) identical vehicles, we consider a scheduling problem of the vehicles on the path. Each vertex \(v_j\) in \(G\) has exactly one job \(j\). Any of the \(n\) jobs must be served by some vehicle. Each job \(j\) has a release time \(r_j\) and a handling time \(h_j\). A travel time \(w_e\), is associated with each edge \(e\). The problem asks to find an optimal schedule of the \(m\) vehicles that minimizes the maximum completion time of all jobs. It is already known that the problem is NP-hard for any fixed \(m\geq 2\). In this paper, we first present an \(O(mn^2)\) time 2-approximation algorithm to the problem, by using properties of optimal gapless schedules. We then give a nearly linear time algorithm that delivers a \((2+\varepsilon)\)-approximation solution for any fixed \(\varepsilon>0\).

MSC:

68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asano, T.; Katoh, N.; Kawashima, K., A new approximation algorithm for the capacitated vehicle routing problem on a tree, J Combin. Optim., 5, 213-231 (2001) · Zbl 1039.90007
[2] Averbakh, I.; Berman, O., Routing and location-routing \(p\)-delivery men problems on a path, Transportation Sci., 28, 162-166 (1994) · Zbl 0807.90054
[3] Averbakh, I.; Berman, O., Sales-delivery man problems on treelike networks, Networks, 25, 45-58 (1995) · Zbl 0833.90036
[4] Averbakh, I.; Berman, O., A heuristic with worst-case analysis for minmax routing of two traveling salesmen on a tree, Discrete Appl. Math., 68, 17-32 (1996) · Zbl 0848.90117
[5] Averbakh, I.; Berman, O., \((p\)−1)/\((p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective, Discrete Appl. Math., 75, 201-216 (1997) · Zbl 0879.68077
[6] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[7] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and schedulinga survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[8] L.A. Hall, D.B. Shmoys, Approximation schemes for constrained scheduling problems, Proceedings of 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 134-139.; L.A. Hall, D.B. Shmoys, Approximation schemes for constrained scheduling problems, Proceedings of 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 134-139.
[9] Karuno, Y.; Nagamochi, H.; Ibaraki, T., Vehicle scheduling on a tree to minimize maximum lateness, J. Oper. Res. Soc. Japan, 39, 345-355 (1996) · Zbl 0873.90051
[10] Karuno, Y.; Nagamochi, H.; Ibaraki, T., Vehicle scheduling on a tree with release and handling times, Ann. Oper. Res., 69, 193-207 (1997) · Zbl 0880.90037
[11] Karuno, Y.; Nagamochi, H.; Ibaraki, T., Computational complexity of the traveling salesman problem on a line with deadlines and general handling times, Mem. Fac. Eng. Design, Kyoto Inst. Tech., 45, 19-22 (1997) · Zbl 0970.90107
[12] Karuno, Y.; Nagamochi, H.; Ibaraki, T., Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks, Networks, 39, 203-209 (2002) · Zbl 1024.90008
[13] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985.; E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985. · Zbl 0562.00014
[14] Nagamochi, H.; Mochizuki, K.; Ibaraki, T., Complexity of the single vehicle scheduling problem on graphs, Inform. Systems Oper. Res., 35, 256-276 (1997) · Zbl 0894.90081
[15] Nagamochi, H.; Mochizuki, K.; Ibaraki, T., Solving the single-vehicle scheduling problems for all home locations under depth-first routing on a tree, IEICE Trans.: Fund., E84-A, 1135-1143 (2001)
[16] Psaraftis, H.; Solomon, M.; Magnanti, T.; Kim, T., Routing and scheduling on a shoreline with release times, Management Sci., 36, 212-223 (1990) · Zbl 0701.90050
[17] Tsitsiklis, J. N., Special cases of traveling salesman and repairman problems with time windows, Networks, 22, 263-282 (1992) · Zbl 0819.90124
[18] Young, G. H.; Chan, C.-L., Single-vehicle scheduling with time window constraints, J. Scheduling, 2, 175-187 (1999) · Zbl 0941.90042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.