Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs

This paper addresses the two-stage assembly flow-shop scheduling problem with non-identical assembly machines at the second stage to minimize a sum of holding and delay costs. Although there are more than one assembly machine in many manufacturing systems, to the best of our knowledge, the two-stage assembly flow-shop scheduling problem (TSAFSP) has never been addressed with more than one assembly machine at stage two. Moreover, setup time is an inevitable factor in many cases and so in this paper, for more reality, sequence dependent setup times are considered for both stages. After extending mathematical modeling, to solve the addressed problem, four hybrid meta-heuristics are developed. A simulated annealing algorithm (SA) and an imperialist competitive algorithm (ICA) in order to find a sequence of jobs at the first stage and a heuristic (HEU) and again SA for assigning addressed jobs to assembly machines in stage two; therefore, these hybrid meta-heuristics are SA+HEU, ICA+HEU, SA+SA and ICA+SA. Computational results reveal that ICA+HEU outperforms all other algorithms; however, the run time of SA+HEU is the smallest among the algorithms.