FINDING PLACEMENT SEQUENCES AND BIN LOCATIONS FOR CARTESIAN ROBOTS

Abstract

Abstract We model the repetitive placement by a Cartesian robot of n parts on a rectangular workpiece. There are n bins or feeders (one per part), to be placed around the boundary of the workpiece, which contain the parts. The robot picks a part from a bin, places it, picks another part, places it, etc.; any placement sequence is possible. The problem, to find bin locations and a placement sequence to minimize total assembly time, is formulated as a traveling salesman problem (on a graph with n nodes) with special structure. This structure allows the computation of a lower bound on the minimum total assembly time in order n effort. The lower bound improves as n increases, and leads to a simple solution algorithm which gives asymptotically optimal solutions in order n log n effort. For die case where parts are uniformly distributed on the workpiece, we give simple closed-form expressions for the expected value of the lower bound. These expressions should be helpful for design decisions; for example, holding n constant, they indicate that square workpieces require more assembly time than non-square, rectangular workpieces of the same area. Most of our results are relatively insensitive to the inclusion of robot acceleration/deceleration effects.