Assembly planning by disjunctive programming and geometrical reasoning

Abstract The challenge in modeling and solving assembly planning problems lies in integrating combinatorial optimization techniques for finding efficient task sequences and resource assignments with geometrical reasoning to ensure the geometrical and technological feasibility of the assembly plans. This paper proposes a Benders decomposition approach that separates the macro-level planning problem, responsible for task sequencing and resource assignment, from micro-level validation on detailed geometrical and technological models. Feedback from the micro to the macro level is provided in the form of disjunctive constraints generated during search, which precludes the repeated occurrence of the collisions encountered in earlier iterations. A disjunctive programming approach is proposed to solve the macro-level planning problem with the added constraints. The efficiency of the approach is demonstrated both in industrial case studies and in computational experiments on generated problem instances.