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

Abstract

This paper presents a local optimization algorithm for minimizing the number of transporters required 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 that a job can remain at a particular stage is restricted by a time window. The transporters that perform the operations move on a shared track, and traffic collisions must be avoided during their movements. To avoid traffic collisions, the operations are partitioned into groups, where each group is served by a single transporter. A local optimal solution is obtained when the group sizes are maximized. We show that 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 die proposed algorithm achieves die global optimal solution are discussed. The algorithm's performance is evaluated on both randomly generated test problems and benchmark problems.