Mixed Integer linear programming and constraint programming models for the online printing shop scheduling problem

Autor(es)

Lunardi, Willian T. ^[1] ; Birgin, Ernesto G. ^[2] ; Laborie, Philippe ^[3] ; Ronconi, Debora P. ^[4] ; Voos, Holger ^[1]

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

^[1] Univ Luxembourg, 29 John F Kennedy, L-1855 Luxembourg - Luxembourg

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

^[3] IBM France, 9 Rue Verdun, BP 85, F-94253 Gentilly - France

^[4] Univ Sao Paulo, Polytech Sch, Dept Prod Engn, Av Prof Luciano Cualberto 1380, Cidade Univ, BR-05508010 Sao Paulo, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 123, NOV 2020.
• Citações Web of Science: 0

Resumo

In this work, the online printing shop scheduling problem is considered. This challenging real problem, that appears in the nowadays printing industry, can be seen as a flexible job shop scheduling problem with sequence flexibility in which precedence constraints among operations of a job are given by an arbitrary directed acyclic graph. In addition, several complicating particularities such as periods of unavailability of the machines, resumable operations, sequence-dependent setup times, partial overlapping among operations with precedence constraints, release times, and fixed operations are also present in the addressed problem. In the present work, mixed integer linear programming and constraint programming models for the minimization of the makespan are presented. Modeling the problem is twofold. On the one hand, the problem is precisely defined. On the other hand, the capabilities and limitations of a commercial software for solving the models are analyzed. Extensive numerical experiments with small-, medium-, and large-sized instances are presented. Numerical experiments show that the commercial solver is able to optimally solve only a fraction of the small-sized instances when considering the mixed integer linear programming model; while all small-sized and a fraction of the mediumsized instances are optimally solved when considering the constraint programming formulation of the problem. Moreover, the commercial solver is able to deliver feasible solutions for the large-sized instances that are of the size of the instances that appear in practice. (C) 2020 Elsevier Ltd. 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: 18/24293-0 - Métodos computacionais de otimização
• Beneficiário: Sandra Augusta Santos
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático