Improved combinatorial Benders decomposition for a scheduling problem with unrelated parallel machines
type: Item
instance of: scholarly article
title: Improved combinatorial Benders decomposition for a scheduling problem with unrelated parallel machines
zbMATH Open document ID: 1437.90077
DOI: 10.1155/2017/9452762
author: Francisco Regis Abreu Gomes
author: Geraldo Robson Mateus
published in: Journal of Applied Mathematics
publication date: 2019-03-18T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C11
zbMATH DE Number: 7037495
Wikidata QID: Q59145194
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2017/9452762
OpenAlex ID: W2724851396
cites work: Q4546261
cites work: The significance of reducing setup times/setup costs
cites work: Q4380372
cites work: Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times
cites work: A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times
cites work: Q3455613
cites work: Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighbourhood search
cites work: A hybrid method for the planning and scheduling
cites work: An integrated method for planning and scheduling to minimize tardiness
cites work: Planning and Scheduling by Logic-Based Benders Decomposition
cites work: Scheduling projects with multi-skilled personnel by a hybrid MILP/CP Benders decomposition algorithm
cites work: Single-facility scheduling by logic-based Benders decomposition
cites work: Partitioning procedures for solving mixed-variables programming problems
cites work: Logic-based Benders decomposition
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: On generating maximal nondominated Benders cuts
cites work: Practical enhancements to the Magnanti-Wong method
cites work: Accelerating Benders decomposition by local branching
cites work: Accelerating Benders method using covering cut bundle generation
cites work: Speed-up Benders decomposition using maximum density cut (MDC) generation
cites work: Strategies for protecting supply chain networks against facility and transportation disruptions: an improved Benders decomposition approach
cites work: A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
cites work: Multicommodity Distribution System Design by Benders Decomposition
cites work: Large-scale mixed integer programming: Benders-type heuristics
cites work: Local branching
cites work: Improving Benders decomposition using a genetic algorithm
cites work: Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs
cites work: A Benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture
cites work: Acceleration strategies of Benders decomposition for the security constraints power system expansion planning
cites work: Multicut Benders decomposition algorithm for process supply chain planning under uncertainty
cites work: Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
cites work: Algorithms for hybrid MILP/CP models for a class of optimization problems
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Minimizing average completion time in the presence of release dates
cites work: A polyhedral approach to single-machine scheduling problems.
description: scientific article; zbMATH DE number 7037495