Scheduling in repetitive manufacturing systems: Complexity, heuristic algorithms and system design

The theory of sequencing and scheduling, more than any other area in operations research, is characterized by large number of problem types. Each type of industry and production manufacturing system has its own sets of rules and requirements that demands different kind of scheduling methods. In recent years, as the application of Just-In-Time (J-I-T) production systems become more popular, scheduling researchers have turned their attention into cyclic scheduling, which is compatible with the concept of J-I-T. This thesis deals with the study of the theory of cyclic scheduling and the manner in which it applies to class of problems that arise in the scheduling of robotic cells.;We review the computational complexity of cyclic scheduling problems and provide proof of NP-completeness for problems which remain open as to complexity.;For the two machine robot cell scheduling problem, we provide a polynomial time algorithm that simultaneously optimizes the robot move and part sequencing problems. We address an important conjecture about the optimality of repeating one unit cycles in a three machine cell and show that such procedure dominates more complicated cycles producing two units.;We investigate the computational complexity of robot scheduling problems in large cells and in the case where the number of part-types is fixed. In particular in a three machine cell producing multiple part-types, we prove that four out of the six potentially optimal robot move cycles for producing one unit allow efficient identification of the optimal part sequence. However, if either of the other two cycles is used, the recognition version of the part sequencing problem is unary NP-complete. Therefore we describe and test simple heuristic procedures for the cell configurations where the part scheduling problem is untractable. The process by which a robotic cell converges to a steady state is investigated.;We also discuss tradeoffs between throughput rate and inventory from combining minimal part sets and the design of cells and buffers within a larger manufacturing environment.