A New One-Machine Decomposition Technique for Solving the Permutation Flow-Shop Scheduling Problem

Existing metaheuristics for the permutation flow-shop scheduling problem primarily explore the search space directly. This study presents a new decomposition technique that, unlike those methods, repeatedly solves one-machine subproblems and extends their solutions to all machines in order to minimize the makespan objective. To this end, the proposed algorithm solves the one-machine problem using a novel forward-backward procedure and extends its solutions to all machines through recurrent displacement of jobs. The improvement of the current solution proceeds until no optimal permutation for a single machine can improve the overall permutation for all machines, gradually improving current solutions and directing the search towards obtaining high-quality solutions. To further improve the results, any solution proposed by the one-machine solution strategy is refined by a local search process. An innovative triangular mechanism is also proposed for constructing initial solutions, with the aim of providing a high-quality starting point for the algorithm. The results of computational experiments not only demonstrate the efficiency of the one-machine forward-backward technique, but also indicate that the algorithm is both robust and highly effective in solving the standard benchmark instances.