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 条
  • [1] A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines
    Nonner, Tim
    Souza, Alexander
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2009, 5573 : 24 - 35
  • [2] 2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times
    Karuno, Y
    Nagamochi, H
    DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) : 433 - 447
  • [3] A local search 4/3-approximation algorithm for the minimum 3-path partition problem
    Chen, Yong
    Goebel, Randy
    Lin, Guohui
    Liu, Longcheng
    Su, Bing
    Tong, Weitian
    Xu, Yao
    Zhang, An
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (05) : 3595 - 3610
  • [4] A local search 4/3-approximation algorithm for the minimum 3-path partition problem
    Yong Chen
    Randy Goebel
    Guohui Lin
    Longcheng Liu
    Bing Su
    Weitian Tong
    Yao Xu
    An Zhang
    Journal of Combinatorial Optimization, 2022, 44 : 3595 - 3610
  • [5] AN APPROXIMATION ALGORITHM FOR A SINGLE-MACHINE SCHEDULING PROBLEM WITH RELEASE TIMES, DELIVERY TIMES AND CONTROLLABLE PROCESSING TIMES
    NOWICKI, E
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 72 (01) : 74 - 81
  • [6] A simple local 3-approximation algorithm for vertex cover
    Polishchuk, Valentin
    Suomela, Jukka
    INFORMATION PROCESSING LETTERS, 2009, 109 (12) : 642 - 645
  • [7] A 4/3-approximation algorithm for minimum 3-edge-connectivity
    Gubbala, Prabhakar
    Raghavachari, Balaji
    ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS, 2007, 4619 : 39 - +
  • [8] A 2/3-approximation algorithm for vertex-weighted matching
    Al-Herz, Ahmed
    Pothen, Alex
    DISCRETE APPLIED MATHEMATICS, 2022, 308 : 46 - 67
  • [9] A 3-approximation algorithm for the facility location problem with uniform capacities
    Ankit Aggarwal
    Anand Louis
    Manisha Bansal
    Naveen Garg
    Neelima Gupta
    Shubham Gupta
    Surabhi Jain
    Mathematical Programming, 2013, 141 : 527 - 547
  • [10] A 3-approximation algorithm for the facility location problem with uniform capacities
    Aggarwal, Ankit
    Louis, Anand
    Bansal, Manisha
    Garg, Naveen
    Gupta, Neelima
    Gupta, Shubham
    Jain, Surabhi
    MATHEMATICAL PROGRAMMING, 2013, 141 (1-2) : 527 - 547
1234