Solution Methods for a Scheduling Problem with Incompatibility and Precedence Constraints

Authors

  • François-Xavier Meuwly
  • Bernard Ries Universit Paris Dauphine
  • Nicolas Zufferey University of Geneva

Keywords:

Project Scheduling, Local Search, Mixed Graph Coloring

Abstract

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.

Downloads

Published

2010-12-02

How to Cite

Meuwly, F.-X., Ries, B., & Zufferey, N. (2010). Solution Methods for a Scheduling Problem with Incompatibility and Precedence Constraints. Algorithmic Operations Research, 5(2), Pages 75 – 85. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/14273

Issue

Vol. 5 No. 2 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.