Advanced problems in robotic cell scheduling: approximations, parallel machines, and multiple robots

Abstract

This thesis considers three different problems in scheduling operations in bufferless robotic cells that produce identical parts. Finding a multi-unit cyclic solution which minimizes the long-run average time to produce a part is an open problem. Most research has been focused on finding an optimal 1-unit cyclic solution. However, it is known that an optimal multi-unit cyclic solution can be better than an optimal 1-unit cyclic solution for cells with four or more machines. We present polynomial algorithms that produce multi-unit cyclic solutions within a constant factor of the optimum for the three most common classes of robotic cells viz., additive, constant, and Euclidean travel-time. The approximation guarantees obtained for these three classes of cells are 1.5, 1.5, and 4, respectively. Following this is a general analysis of the problem of sequencing operations in bufferless robotic cells with parallel machines. Efficient use of parallel machines requires that several parts be processed in one cycle of robot movements. We analyze such cycles for constant travel-time robotic cells. The results and the analysis in this chapter offer practitioners (i) guidelines to determine whether parallel machines will be cost-effective for a given implementation, (ii) a simple formula for determining how many copies of each machine are required to meet a particular throughput rate, and (iii) an optimal sequence of robot moves for a cell with parallel machines under a certain condition on the processing tunes. This model is then extended to cover cells with parallel machines, multiple robots, and the more general Euclidean travel-times. We describe a plan of operation that allows the robots to operate concurrently, efficiently, and with no risk of colliding. We propose a set of sequences of robot moves that direct each robot's actions. We analytically determine this scheme's throughput, and determine problem instances that are common in practice for which it is optimal. Through simulation, we demonstrate that our scheme is statistically superior to the heuristic dispatching rule currently in use by a Dallas-area semiconductor equipment manufacturer. We also determine conditions under which the manufacturer's scheme is less efficient.