• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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é
External document link
http://journals.hil.unb.ca/index.php/AOR/article/view/14273
Date
2010
Journal name
Algorithmic Operations Research
Volume
5
Number
5
Publisher
Preeminent Academic Facets
Pages
75-85
Metadata
Show full item record
Author(s)
Zufferey, Nicolas
Ries, Bernard
Meuwly, François-Xavier
Abstract (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.
Subjects / Keywords
Precedence Constraints; Incompatibility Constraints; Scheduling Problem

Related items

Showing items related by title and author.

  • Thumbnail
    Separation Algorithms for Single-Machine Scheduling with Precedence Constraints 
    Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Communication / Conférence
  • Thumbnail
    Generalized compressible flows and solutions of the H(div) geodesic problem 
    Gallouët, Thomas; Natale, Andrea; Vialard, François-Xavier (2020) Article accepté pour publication ou publié
  • Thumbnail
    On the complexity of the Eulerian closed walk with precedence path constraints problem 
    Mahjoub, Ali Ridha; Lacroix, Mathieu; Kerivin, Hervé (2010) Communication / Conférence
  • Thumbnail
    On the complexity of the Eulerian closed walk with precedence path constraints problem 
    Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012) Article accepté pour publication ou publié
  • Thumbnail
    A DSS approach for heterogeneous parallel machines scheduling with due windows, processor-&-sequence-dependent setup and proximate supply chain constraints 
    Azzamouri, Ahlam; Essaadi, Imane; Fenies, Pierre; Fontane, Frédéric; Giard, Vincent (2016) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo