A branch-and-cut algorithm for a resource-constrained scheduling problemReport as inadecuate

A branch-and-cut algorithm for a resource-constrained scheduling problem - Download this document for free, or read online. Document in PDF available to download.

1 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes Compiègne 2 LIMOS - Laboratoire d-Informatique, de Modélisation et d-optimisation des Systèmes

Abstract : This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance, in terms of both exact and approximate resolution when the instance size increases.

Keywords : Polyhedral combinatorics scheduling branch-and-cut distributed systems OR in telecommunications

Author: Renaud Sirdey - Hervé Kerivin -

Source: https://hal.archives-ouvertes.fr/


Related documents