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

Author(s)

Birgin, E. G. ^[1] ; Ferreira, J. E. ^[1] ; Ronconi, D. P. ^[2]

Affiliation

^[1] Univ Sao Paulo, Dept Comp Sci, Inst Math & Stat, Rua Matao 1010, Cidade Univ, BR-05508090 Sao Paulo, SP - Brazil

^[2] Univ Sao Paulo, Dept Prod Engn, Polytech Sch, Ave Prof Luciano Gualberto 1380, Cidade Univ, BR-05508010 Sao Paulo, SP - Brazil

• Document type: Journal article
• Source: Computers & Operations Research; v. 114, FEB 2020.
• Web of Science Citations: 0

Abstract

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. (C) 2019 Elsevier Ltd. All rights reserved. (AU)

• FAPESP's process: 18/24293-0 - Computational methods in optimization
• Grantee: Sandra Augusta Santos
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants