Show simple item record

Solution Methods for a Scheduling Problem with Incompatibility and Precedence Constraints

dc.contributor.authorZufferey, Nicolas
dc.contributor.authorRies, Bernard
dc.contributor.authorMeuwly, François-Xavier
dc.date.accessioned2011-05-06T13:38:55Z
dc.date.available2011-05-06T13:38:55Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6208
dc.language.isoenen
dc.subjectPrecedence Constraintsen
dc.subjectIncompatibility Constraintsen
dc.subjectScheduling Problemen
dc.subject.ddc003en
dc.titleSolution Methods for a Scheduling Problem with Incompatibility and Precedence Constraintsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenConsider 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.en
dc.relation.isversionofjnlnameAlgorithmic Operations Research
dc.relation.isversionofjnlvol5en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages75-85en
dc.identifier.urlsitehttp://journals.hil.unb.ca/index.php/AOR/article/view/14273en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherPreeminent Academic Facetsen
dc.subject.ddclabelrecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record