improved combinatorial benders decomposition for a scheduling problem with unrelated parallel machines
Clicks: 134
ID: 256351
2017
Article Quality & Performance Metrics
Overall Quality
Not rated
Combines reader engagement with the AI quality analysis. This
article has not been analysed, so there is no overall score —
reader engagement is measured and shown alongside.
Reader Engagement
Emerging Content
30.0
/100
134 views
40 readers
AI Quality Assessment
Not analyzed
Readership in this journal
EmergingRanked #108 of 357 articles by views in Chemico-biological interactions
Most read
Least read
Bar heights use a square-root scale. Only the 120 most-read articles are drawn; the journal has 357 in total.
Mint this article as an NFT
Not yet mintedCreate a permanent, verifiable on-chain record of this article on the Scimatic Network. The NFT is held in your Journament account, and you can withdraw it to your own wallet at any time.
5
SUSD
one-off · no wallet required
Abstract
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.
| Reference Key |
gomes2017journalimproved
Use this key to autocite in the manuscript while using
SciMatic Manuscript Manager or Thesis Manager
|
|---|---|
| Authors | ;Francisco Regis Abreu Gomes;Geraldo Robson Mateus |
| Journal | Chemico-biological interactions |
| Year | 2017 |
| DOI |
10.1155/2017/9452762
|
| URL | |
| Keywords |
Citations
No citations found. To add a citation, contact the admin at info@scimatic.org
Comments
No comments yet. Be the first to comment on this article.