<  Back to the Polytechnique Montréal portal

Algorithmes de dénombrement d'extensions linéaires d'un ordre partiel et application aux problèmes d'ordonnancement disjonctif

Rachid Cherkaoui El Azzouzi

Master's thesis (2015)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (703kB)
Show abstract
Hide abstract

Abstract

In constraint programming a unary resource constraint is a set of valid permutations of activities each with a time window and a duration. This constraint is generalized if we consider precedence constraints between activities given by a partially ordered set. A disjunctive scheduling problem can be stated as a combination of one or more such constraints for which some additional constraints such as disjunction or sequence of activities on different resources may be added. In this model, a solution is found by a series of decisions on the relative po- sition of a pair of activities on a same resource and for which the order is unknown. The algorithm used to select the pair and the order is called a branching heuristic. In the context of maxSD, densities of all assignments of pairs and order are computed and the assignment of maximum density is selected. In order to adapt this heuristic for scheduling problems with unary resources, we will consider the permutations of the partial order in which the rank of an activity is superior to another. For that, we propose exact and heuristic algorithms that compute the density of permutations in a partially ordered set. These algorithms are then used in branching to solve the constraint satisfaction version of the Job-Shop scheduling problem, a typical use case of scheduling with unary resource constraints.

Résumé

En programmation par contraintes, une contrainte de ressource unaire est un ensemble de permutations valides des activités chacune avec une fenêtre de temps et une durée. Cette contrainte est généralisée si on considère des préséances entre activités données sous la forme d'un ensemble partiellement ordonné. Un problème d'ordonnancement disjonctif peut être modélisé par une ou plusieurs contraintes de ressource unaire auxquelles s'ajoutent des contraintes supplémentaires telles que des disjonctions entre activités de différentes ressources ou des contraintes de séquences. La recherche d'une solution au problème se fait par une série de décisions de la position relative d'une paire d'activités associées à une contrainte dont l'ordre n'est pas encore connu. L'algorithme utilisé dans le choix de la paire ainsi que la position relative est appelé heuristique de branchement. Dans le contexte de l'heuristique maxSD, il s'agit de calculer les densités de solutions de toutes les assignations de paires d'activités à un ordre et ensuite de brancher sur celle de densité maximum. Pour adapter cette heuristique aux problèmes d'ordonnancement avec contraintes de ressource unaire, on considérera les densités de permutations dans lesquelles une activité est placée avant l'autre dans l'ordre partiel associé à chaque contrainte. Pour ce faire, on propose deux algorithmes exact et heuristique pour le calcul des densités de permutations dans un ensemble partiellement ordonné. Ces algorithmes sont utilisés dans l'heuristique de branchement pour résoudre la version de satisfaction de contraintes du problème Job-Shop, un cas typique d'ordonnancement avec ressources unaires.

Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: Gilles Pesant
PolyPublie URL: https://publications.polymtl.ca/2047/
Institution: École Polytechnique de Montréal
Date Deposited: 01 Apr 2016 14:18
Last Modified: 19 Apr 2023 14:23
Cite in APA 7: Cherkaoui El Azzouzi, R. (2015). Algorithmes de dénombrement d'extensions linéaires d'un ordre partiel et application aux problèmes d'ordonnancement disjonctif [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/2047/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item