New exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources
FROGER, Aurélien
Institut de Mathématiques de Bordeaux [IMB]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
Institut de Mathématiques de Bordeaux [IMB]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
SADYKOV, Ruslan
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
FROGER, Aurélien
Institut de Mathématiques de Bordeaux [IMB]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
Institut de Mathématiques de Bordeaux [IMB]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
SADYKOV, Ruslan
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
< Reduce
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
Language
en
Article de revue
This item was published in
European Journal of Operational Research. 2022
Elsevier
Date
2022English Abstract
We study the prize-collecting job sequencing problem with one common and multiple secondary resources. In this problem, a set of jobs is given, each with a profit, multiple time windows for its execution, and a duration ...Read more >
We study the prize-collecting job sequencing problem with one common and multiple secondary resources. In this problem, a set of jobs is given, each with a profit, multiple time windows for its execution, and a duration during which it requires the main resource. Each job also requires a preassigned secondary resource before, during, and after its use of the main resource. The goal is to select and schedule the subset of jobs that maximize the total profit. We present a new mixed integer linear programming formulation of the problem and a branch-cut-and-price algorithm as an exact solution method. We also introduce a heuristic algorithm to tackle larger instances. Extensive numerical experiments show that our exact algorithm can solve to optimality literature instances with up to 500 jobs for a particular dataset and up to 250 jobs for another dataset with different characteristics. Our heuristic builds high-quality solutions in a small computational time. It computes new best-known solutions for most of the larger instances.Read less <
English Keywords
Iterated local search
Branch-cut-and-price
Labeling algorithm
Sequencing
Scheduling
Origin
Hal imported