Complexity of sequencing tasks in assembly cells attended by one or two robots

Abstract

This article develops a structure by which the computational complexity of sequencing problems in assembly cells attended by one or two robots may be evaluated. A taxonomy of cell features that affect complexity is developed, polynomial-time algorithms are presented for certain problems, and borderline designs at which complexity changes dramatically are identified. Results will aid cell designers by indicating classes of designs for which task sequence may be optimized and other classes for which this cannot be done. Designs which entail features that lead to intractable sequencing problems may be modified to maximize cell productivity.