Ordonnancement des systèmes de production sans temps d'arrêt machine
Institution:
Lyon, INSADisciplines:
Directors:
Abstract EN:
Within the general theory of scheduling, it’s the “ no-idle ” constraint which approaches the best our preoccupation. It means that a machine must not stop between its first and last operation. This constraint is only defined within the linear organisations of workshop problems (flow-shop). In this thesis,, three various points are studied. First, we present a branch and bound algorithm. Secondly, we propose a O(0*log(n)) heuristic for the case of permutation flow-shop problems with three machines, next a O(n3) heuristic for the same type of problems with any number of machines. Finally, we treat the partial relaxation of the no-idle constraint in the case of flow-shop problems where a maximum number of idle times are allowed on all machines.
Abstract FR:
Au sein de la théorie générale de l'ordonnancement, la contrainte " no-idle " constitue nos préoccupations. Elle implique qu'un équipement ne doit pas s'arrêter entre sa première et sa dernière utilisation. Cette contrainte ne se définie formellement qu'au sein du sous ensemble des ateliers linéaires (flow-shop), car se sont les seules configurations pour lesquelles la question de l'existence d'une solution sous cette contrainte se pose. Dans cette thèse trois différents points sont successivement traités. Nous étudions, en premier lieu, une solution exacte à travers la conception d'un algorithme de type séparation et évaluation. En second lieu, nous proposons une première heuristique en O(n*log(n)) pour le cas d'un flow-shop de permutation à trois machines, puis une deuxième heuristique en O(n3) pour le cas plus général d'un nombre quelconque de machines. En troisième lieu, nous traitons le cas d'un flow-shop pour lequel un nombre maximum de temps morts sont permis sur l'ensemble des machines.