A greedy algorithm to determine the number of transporters in a cyclic electroplating process

This paper presents a local optimization algorithm for minimizing the number of transporters for material handling in a cyclic processing line. Within a cycle, a given set of transportation operations must be performed. Each operation consists of picking up a work-in-process job at a stage and delivering it to the next stage. The length of time a job can remain at a stage is restricted by a time window. The transporters that perform the operations move on a shared-track and allow no traffic collision during their movement. To avoid traffic collision, the operations are partitioned into groups, each is served by a single transporter. A local optimal solution is obtained when the group sizes are maximized. The duals of the linear programming subproblems formulated in the process of maximizing the group sizes are specially structured shortest path problems. This leads to an effective search method for the maximization problem. Conditions when the proposed algorithm achieves the global optimal solution are discussed. The algorithm´s performance is presented on both randomly generated test problems and benchmark problems