List scheduling and beam search methods for the flexible job shop scheduling problem with sequencing flexibility

Autor(es)

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

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Math & Stat, Dept Comp Sci, BR-05508090 Sao Paulo - Brazil

^[2] Univ Sao Paulo, Polytech Sch, Dept Prod Engn, BR-05508900 Sao Paulo - Brazil

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 247, n. 2, p. 421-440, DEC 1 2015.
• Citações Web of Science: 14

Resumo

An extended version of the flexible job shop problem is tackled in this work. The considered extension to the classical flexible job shop problem allows the precedences between the operations to be given by an arbitrary directed acyclic graph instead of a linear order. Therefore, the problem consists of allocating the operations to the machines and sequencing them in compliance with the given precedences. The goal in the present work is the minimization of the makespan. A list scheduling algorithm is introduced and its natural extension to a beam search method is proposed. Numerical experiments assess the efficiency of the proposed approaches. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved. (AU)

• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produção, e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/05475-7 - Métodos computacionais de otimização
• Beneficiário: Sandra Augusta Santos
• Modalidade de apoio: Auxílio à Pesquisa - Temático