The distributed permutation flow shop to minimise the total flowtime

Abstract

In the last years, researchers are paying special attention to scheduling in distributed environments due to the increasing benefits of multi-factory manufacture. In this paper, we address the distributed permutation flowshop scheduling problem to minimise the total flowtime. Since, to the best of our knowledge, this problem has not been addressed previously, we first analyse it and discuss several properties, theorems, assignment rules, representation of the solutions and speed-up procedures. Given that the problem is NP-hard, we focus on approximate procedures, and propose eighteen constructive heuristics to obtain high-quality solutions in reasonable CPU times. In addition, we propose an iterative improvement algorithm to further refine the so-obtained solutions. The extensive computational experience carried out shows that the proposed method outperforms several metaheuristics adapted from related scheduling problems.