Scheduling complex products with assembly operations in hybrid flow shop environment

The hybrid flowshop scheduling problem with assembly operations is dealt with in this study in which the hybrid flowshop is followed by single assembly machine. Each final product has predefined structure and includes several parts with known bill of material (BOM). Parts are firstly processed in hybrid flowshop and thereafter, assembled based on structure of products. Each product has assembly operation(s) and the product is considered complete once its last assembly operation is processed. The goal is to find a schedule which minimizes the last product completion time. For the addressed problem, a mathematical model is developed and two heuristic algorithms as well as two meta-heuristic ones based on Ant Colony Optimization (ACO) are then proposed to solve the large-scale instances. The heuristic algorithms are developed versions of the existing well-known techniques which are employed to tackle the mentioned problem in two phases:1) finding the sequence of assembly operations/products, 2) finding the parts sequence. Due to precedence relation of parts and assembly operation, two versions of the ACO algorithm are proposed. The first version is basic ACO which has been adapted to the studied problem however the second one uses two pheromones where the first pheromone is employed to find the sequence of assembly operations and the second one is designed to find the parts sequence. Also, a lower bound based on the bottleneck stage is then proposed. In order to test efficiency of the methods, a comprehensive experiment is conducted.