The distributed permutation flow shop to minimise the total flowtime. (April 2018) - Fernandez-Viagas, Victor; Perez-Gonzalez, Paz; Framinan, Jose M.
Highlights: We address the distributed permutation flow shop for total flowtime. We propose eighteen constructive heuristics to efficiently solve the problem. We propose a simple evolutionary algorithm for the problem. We present several properties and assignment rules for the problem. We compare the proposal with efficient algorithms in the literature. 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.