ترجمه مقاله موقعیت یابی وسایل هدایت شونده اتوماتیک در یک طرح حلقه - نشریه الزویر

We address the problem of determining the home positions for m automated guided vehicles (AGVs) in a loop layout where n pickup points are positioned along the circumference m < n†. A home position is the location where idle AGVs are held until they are assigned to the next transportation task. The home positions need to be selected so as to minimize an objective function of the response times, where the response time for a pickup point is de®ned as the travel time to the pickup point from the nearest home location. For the unidirectional ¯ow system, where all AGVs can move in one direction only, we ®rst point out that the problem of minimizing an arbitrary regular cost function can quite straightforwardly be solved in O n2† time if m ˆ 1 and in O mnm† time if m P 2, which is polynomial for a ®xed number m of AGVs. For m P3, we can do better, however: we derive a generic O mn3† time and O mn† space dynamic programming algorithm for minimizing any regular function of the response times. For minimizing maximum response time a further gain in eciency is possible: this problem can be solved in O n2† time if m ˆ 2 and O n2 log n† time if m P3. Our results improve on earlier published work, where it was suggested that problems with m P 2 are NP-hard. For the bidirectional ¯ow system, where the AGVs can move in both directions, the problem of determining the home locations is inherently much more dicult. Important objective functions like average response time and maximum response time can nonetheless still be minimized by the same types of algorithms and in the same amount of time as their unidirectional counterparts, once restrictive conditions apply such that the case m ˆ 1 can be solved in polynomial time. One such restrictive condition is that each AGV travels at constant speed. Ó 2000 Elsevier Science B.V. All rights reserved.