![](/images/graphics-bg.png)
Improved Combinatorial Benders Decomposition for a Scheduling Problem with Unrelated Parallel Machines
Joint Authors
Gomes, Francisco Regis Abreu
Mateus, Geraldo Robson
Source
Journal of Applied Mathematics
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-07-03
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
This paper addresses the unrelated parallel machines scheduling problem with sequence and machine dependent setup times.
Its goal is to minimize the makespan.
The problem is solved by a combinatorial Benders decomposition.
This method can be slow to converge.
Therefore, three procedures are introduced to accelerate its convergence.
The first procedure is a new method that consists of terminating the execution of the master problem when a repeated optimal solution is found.
The second procedure is based on the multicut technique.
The third procedure is based on the warm-start.
The improved Benders decomposition scheme is compared to a mathematical formulation and a standard implementation of Benders decomposition algorithm.
In the experiments, two test sets from the literature are used, with 240 and 600 instances with up to 60 jobs and 5 machines.
For the first set the proposed method performs 21.85% on average faster than the standard implementation of the Benders algorithm.
For the second set the proposed method failed to find an optimal solution in only 31 in 600 instances, obtained an average gap of 0.07%, and took an average computational time of 377.86 s, while the best results of the other methods were 57, 0.17%, and 573.89 s, respectively.
American Psychological Association (APA)
Gomes, Francisco Regis Abreu& Mateus, Geraldo Robson. 2017. Improved Combinatorial Benders Decomposition for a Scheduling Problem with Unrelated Parallel Machines. Journal of Applied Mathematics،Vol. 2017, no. 2017, pp.1-10.
https://search.emarefa.net/detail/BIM-1170039
Modern Language Association (MLA)
Gomes, Francisco Regis Abreu& Mateus, Geraldo Robson. Improved Combinatorial Benders Decomposition for a Scheduling Problem with Unrelated Parallel Machines. Journal of Applied Mathematics No. 2017 (2017), pp.1-10.
https://search.emarefa.net/detail/BIM-1170039
American Medical Association (AMA)
Gomes, Francisco Regis Abreu& Mateus, Geraldo Robson. Improved Combinatorial Benders Decomposition for a Scheduling Problem with Unrelated Parallel Machines. Journal of Applied Mathematics. 2017. Vol. 2017, no. 2017, pp.1-10.
https://search.emarefa.net/detail/BIM-1170039
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1170039