ملخص: 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 -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].

لغة: إنجليزية