• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Doctoral Thesis
DOI
10.11606/T.45.2016.tde-20102016-123243
Document
Author
Full name
Wellington Donizeti Previero
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2016
Supervisor
Committee
Ferreira, Carlos Eduardo (President)
Araujo, Silvio Alexandre de
Gruber, Aritanan Borges Garcia
Maculan Filho, Nelson
Ronconi, Debora Pretti
Title in Portuguese
Estratégias de resolução para o problema de job-shop flexível
Keywords in Portuguese
Branch and cut
Inequações válidas
Job-shop flexível
Matheuristcs
Abstract in Portuguese
Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs
Title in English
Solution approaches for flexible job-shop scheduling problem
Keywords in English
Branch and cut
Flexible job-shop
Matheuristics
Valid inequalities
Abstract in English
This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2016-10-31
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.