Solution Methods for a Scheduling Problem with Incompatibility and Precedence Constraints
Zufferey, Nicolas; Ries, Bernard; Meuwly, François-Xavier (2010), Solution Methods for a Scheduling Problem with Incompatibility and Precedence Constraints, Algorithmic Operations Research, 5, 5, p. 75-85
Type
Article accepté pour publication ou publiéLien vers un document non conservé dans cette base
http://journals.hil.unb.ca/index.php/AOR/article/view/14273Date
2010Nom de la revue
Algorithmic Operations ResearchVolume
5Numéro
5Éditeur
Preeminent Academic Facets
Pages
75-85
Métadonnées
Afficher la notice complèteRésumé (EN)
Consider a project which consists in a set of operations to be performed, assuming the processing time of each operation is at most one time period. In this project, precedence and incompatibility constraints between operations have to be satisfied. The goal is to assign a time period to each operation while minimizing the duration of the whole project and while taking into account all the constraints. Based on the mixed graph coloring model and on an efficient and quick tabu search algorithm for the usual graph coloring problem, we propose a tabu search algorithm as well as a variable neighborhood search heuristic for the considered scheduling problem. We formulate an integer linear program (useful for the CPLEX solver) as well as a greedy procedure for comparison considerations. Numerical results are reported on instances with up to 500 operations.Mots-clés
Precedence Constraints; Incompatibility Constraints; Scheduling ProblemPublications associées
Affichage des éléments liés par titre et auteur.
-
Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Communication / Conférence
-
Gallouët, Thomas; Natale, Andrea; Vialard, François-Xavier (2020) Article accepté pour publication ou publié
-
Jeunet, Jully; Salassa, Fabio (2022) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Lacroix, Mathieu; Kerivin, Hervé (2010) Communication / Conférence
-
Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012) Article accepté pour publication ou publié