A 5/3-approximation algorithm for scheduling vehicles on a path with release and handling times

被引：20
作者：
Gaur, DR [1 ]
Gupta, A
Krishnamurti, R
机构：
[1] Univ Lethbridge, Dept Math & Comp Sci, Lethbridge, AB T1K 3M4, Canada
[2] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada
来源：
INFORMATION PROCESSING LETTERS | 2003年 / 86卷 / 02期
关键词：
approximation algorithms; design of algorithms;
D O I：
10.1016/S0020-0190(02)00474-X
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper we study a particular type of vehicle routing problem that arises in the context of scheduling an automatic guided vehicle (AGV) in the Flexible Manufacturing paradigm. Here we consider the problem of scheduling the vehicle when the sites are located on a path and the depot is at some arbitrary location. The objective is to determine the schedule with minimum completion time such that each site is visited only after its release time and handling times are taken into consideration. We provide a 5/3-approximation algorithm for the same. This improves the previous approximation ratio of 2 due to Karuno, Nagamochi and Ibaraki [Ann. Oper. Res. 69 (1997) 193-207]. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：87 / 91
页数：5
相关论文
共 31 条
  • [21] A 5/4-approximation algorithm for scheduling identical malleable tasks
    Decker, T.
    Luecking, T.
    Monien, B.
    THEORETICAL COMPUTER SCIENCE, 2006, 361 (2-3) : 226 - 240
  • [22] A 4/3-APPROXIMATION ALGORITHM FOR THE MINIMUM 2-EDGE CONNECTED MULTISUBGRAPH PROBLEM IN THE HALF-INTEGRAL CASE
    Boyd, Sylvia
    Cheriyan, Joseph
    Cummings, Robert
    Grouts, Logan
    Ibrahimpur, Sharat
    Szigeti, Zoltan
    Wang, Lu
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (03) : 1730 - 1747
  • [23] AN APPROXIMATION ALGORITHM FOR THE M-MACHINE PERMUTATION FLOW-SHOP SCHEDULING PROBLEM WITH CONTROLLABLE PROCESSING TIMES
    NOWICKI, E
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 70 (03) : 342 - 349
  • [24] A (3/2+ε)-approximation algorithm for scheduling on two parallel machines with job delivery coordination
    Chen, Yong
    Zhang, An
    Tan, Zhiyi
    Xue, Ying
    Chen, Guangting
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2021, 72 (09) : 1929 - 1942
  • [25] A (5/3+ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
    Grandoni, Fabrizio
    Moemke, Tobias
    Wiese, Andreas
    Zhou, Hang
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 607 - 619
  • [26] A 6/5-approximation algorithm for the maximum 3-cover problem
    Caragiannis, Toannis
    Monaco, Gianpiero
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008, PROCEEDINGS, 2008, 5162 : 205 - +
  • [27] A 6/5-approximation algorithm for the maximum 3-cover problem
    Caragiannis, Ioannis
    Monaco, Gianpiero
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (01) : 60 - 77
  • [28] A 6/5-approximation algorithm for the maximum 3-cover problem
    Ioannis Caragiannis
    Gianpiero Monaco
    Journal of Combinatorial Optimization, 2013, 25 : 60 - 77
  • [29] 3/2-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
    Rathinam, Sivakumar
    Sengupta, Raja
    OPERATIONS RESEARCH LETTERS, 2010, 38 (01) : 63 - 68
  • [30] An LP-based 3/2-approximation algorithm for the s-t path graph Traveling Salesman Problem
    Gao, Zhihan
    OPERATIONS RESEARCH LETTERS, 2013, 41 (06) : 615 - 617
1234