×

Single-vehicle scheduling problems with release and service times on a line. (English) Zbl 1207.90061

Summary: We consider the following vehicle scheduling problem. There are some customers on a line that will be served by a single vehicle. Each customer is associated with a release time and a service time. The objective is to schedule the vehicle to minimize the makespan. For the tour version, where the makespan means the time when the vehicle has served all customers and returned back to its initial location, we present a 3/2-approximation algorithm. For the path version, where the makespan is defined as the time by which the last customer has been served completely, we present a 5/3-approximation algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afrati, The complexity of the traveling repairman problem, Inform Theor Appl 20 pp 79– (1986) · Zbl 0585.68057
[2] Augustine, Linear time approximation schemes for vehicle scheduling problems, Theor Comput Sci 324 pp 147– (2004) · Zbl 1091.90015
[3] Averbakh, Routing and location-routing p-delivery men problems on a path, Transport Sci 28 pp 162– (1994) · Zbl 0807.90054
[4] García, A note on the traveling repairman problem, Networks 40 pp 27– (2002) · Zbl 1027.90104
[5] Gaur, A \({5 \over 3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times, Inf Process Lett 86 pp 87– (2003) · Zbl 1156.90363
[6] Y. Karuno H. Nagamochi T. Ibaraki A 1.5-approximation for single vehicle scheduling problem on a line with release and handling times 1998 1363 1368
[7] Karuno, Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks, Networks 39 pp 203– (2002) · Zbl 1024.90008
[8] Karuno, 2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times, Discrete Appl Math 129 pp 433– (2003) · Zbl 1034.68122
[9] Karuno, An approximability result of the multi-vehicle scheduling problem on a path with release and handling times, Theor Comput Sci 312 pp 267– (2004) · Zbl 1067.90143
[10] Psaraftis, Routing and scheduling on a shoreline with release times, Manage Sci 36 pp 212– (1990) · Zbl 0701.90050
[11] Simchi-Levi, Minimizing the total flow time of n jobs on a network, IIE Trans 23 pp 236– (1991)
[12] R.A. Sitters Complexity and approximation in routing and scheduling 2004
[13] Tsitsiklis, Special cases of traveling salesman and repairman problems with time windows, Networks 22 pp 263– (1992) · Zbl 0819.90124
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.