Iterative beam search algorithms for the permutation flowshop

In the flowshop problem, one has to schedule jobs, where each job has to follow the same route of machines. The goal is to find a job order that minimizes some criteria. The permutation flowshop, also called PFSP, is a common (and fundamental) variant that imposes the machines to process jobs in the same order (thus, a permutation of jobs is enough to describe a solution). The permutation flowshop has been one of the most studied problems in the literature [35, 30] and has been considered on various industrial applications [16, 42]. We may also note that the permutation flowshop is at the origin of multiple other variants, for instance, the blocking permutation flowshop [45], the multiobjective permutation flowshop [20], the distributed permutation flowshop [11], the no-idle permutation flowshop [31], the permutation flowshop with buffers [28] and many others. Regarding the criteria to minimize, we study in this paper, two of the most studied objectives: the makespan (minimizing the completion time of the last job on the last machine) and the flowtime (minimizing the sum of completion times of each job on the last machine).