The search functionality is under construction.

The search functionality is under construction.

We consider a single-vehicle scheduling problem on a tree, where each vertex has a job with a release time and a processing time and each edge has a travel time. There is a single vehicle which starts from a start vertex *s* and reaches a goal vertex *g* after finishing all jobs. In particular, *s* is called a home location if *s* = *g*. The objective of the problem is to find a depth-first routing on *T* so as to minimize the completion time. In this paper, we first show that the minimum completion times of the problem for all home locations *s**V* can be simultaneously computed in *O*(*n*) time, once the problem with a specified home location *s**V* has been solved, where *n* is the number of vertices. We also show that given a specified start vertex *s*, the minimum completion times for all goal vertices *g* can be computed in *O*(*n*) time.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1135-1143

- Publication Date
- 2001/05/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hiroshi NAGAMOCHI, Koji MOCHIZUKI, Toshihide IBARAKI, "Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 5, pp. 1135-1143, May 2001, doi: .

Abstract: We consider a single-vehicle scheduling problem on a tree, where each vertex has a job with a release time and a processing time and each edge has a travel time. There is a single vehicle which starts from a start vertex *s* and reaches a goal vertex *g* after finishing all jobs. In particular, *s* is called a home location if *s* = *g*. The objective of the problem is to find a depth-first routing on *T* so as to minimize the completion time. In this paper, we first show that the minimum completion times of the problem for all home locations *s**V* can be simultaneously computed in *O*(*n*) time, once the problem with a specified home location *s**V* has been solved, where *n* is the number of vertices. We also show that given a specified start vertex *s*, the minimum completion times for all goal vertices *g* can be computed in *O*(*n*) time.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1135/_p

Copy

@ARTICLE{e84-a_5_1135,

author={Hiroshi NAGAMOCHI, Koji MOCHIZUKI, Toshihide IBARAKI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree},

year={2001},

volume={E84-A},

number={5},

pages={1135-1143},

abstract={We consider a single-vehicle scheduling problem on a tree, where each vertex has a job with a release time and a processing time and each edge has a travel time. There is a single vehicle which starts from a start vertex *s* and reaches a goal vertex *g* after finishing all jobs. In particular, *s* is called a home location if *s* = *g*. The objective of the problem is to find a depth-first routing on *T* so as to minimize the completion time. In this paper, we first show that the minimum completion times of the problem for all home locations *s**V* can be simultaneously computed in *O*(*n*) time, once the problem with a specified home location *s**V* has been solved, where *n* is the number of vertices. We also show that given a specified start vertex *s*, the minimum completion times for all goal vertices *g* can be computed in *O*(*n*) time.

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1135

EP - 1143

AU - Hiroshi NAGAMOCHI

AU - Koji MOCHIZUKI

AU - Toshihide IBARAKI

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E84-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2001

AB - We consider a single-vehicle scheduling problem on a tree, where each vertex has a job with a release time and a processing time and each edge has a travel time. There is a single vehicle which starts from a start vertex *s* and reaches a goal vertex *g* after finishing all jobs. In particular, *s* is called a home location if *s* = *g*. The objective of the problem is to find a depth-first routing on *T* so as to minimize the completion time. In this paper, we first show that the minimum completion times of the problem for all home locations *s**V* can be simultaneously computed in *O*(*n*) time, once the problem with a specified home location *s**V* has been solved, where *n* is the number of vertices. We also show that given a specified start vertex *s*, the minimum completion times for all goal vertices *g* can be computed in *O*(*n*) time.

ER -