A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs

• Published in: Computers & operations research 2020-02, Vol.114, p.104824, Article 104824
• Main Authors: Birgin, E.G., Ferreira, J.E., Ronconi, D.P.
• Format: Article
• Language: English
• Subjects: Beam search; Common due date; Earliness and tardiness; Flowshop; Heuristics; Integer programming; Job shops; Mixed integer; Operations research; Optimization; Permutations; Production scheduling; Scheduling; Search algorithms; Search methods; Waiting time
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.104824

•The m-machine permutation flowshop scheduling problem is considered in the present work.•The main goal is the minimization of the absolute deviation of job completion times from a common due date.•Among solutions that minimize the main goal, we seek choosing one that minimizes the sum of the waiting times of the jobs.•A detailed description of the introduced heuristic methods allows fully reproducibility. This paper addresses the minimization of the absolute deviation of job completion times from a common due date in a flowshop scheduling problem. Besides this main objective, the minimization of the waiting time of the jobs in the production environment, that can be seen as an intermediate inventory cost, is also considered. Initially, a mixed integer programming model for this problem is proposed and, due to its complexity, heuristic approaches are developed. A list-scheduling algorithm for the approached problem is introduced. Moreover, a filtered beam search method that explores specific characteristics of the considered environment is proposed. Numerical experiments show that the presented methods can be successfully applied to this problem.