Job Shop: simulation de production de pièces de l'ordre NC

Introduction

Nous nous proposons de reprendre le problème de Job Shop précédemment simulé par un programme C++, sous le logiciel QNAP2.

Pour rappel, le Job Shop est un problème NP-complet ce pourquoi la simulation est nécessaire.

Il s’agit de simuler le fonctionnement d’un atelier disposant de M machines et fabriquant des pièces de N gammes différentes.

Chaque gamme se différencie par l’ordre et le temps de passage d’une pièce sur les machines.

Nous effectuons la simulation de la production de NC pièces d’ordre donnée sur cet atelier.

Le programme QNAP aura donc pour objectif de déterminer le makespan.

La simulation telle que définie ci-dessus ne donne pas le meilleur makespan possible pour un ensemble de pièces d’entrée, mais uniquement le makespan associé à l’ordre des pièces défini en entrée !

Or l’optimisation de ce makespan est un objectif afin de gagner en productivité et compétitivité.

Nous allons donc dans un second temps considérer une méthode d’amélioration de type descente stochastique afin de trouver le meilleur ordre d’entrée des pièces i.e. celui qui donne le makespan le plus petit possible.

A travers ce rapport, nous chercherons donc à expliquer comment QNAP permet de résoudre les deux problématiques développées ci-dessus, et exposerons les résultats obtenus.

I Job Shop

1 Structures et hypothèses:

Les données du problème sont stockées dans des variables globales : matrices indiquant l’ordre des machines pour une gamme donnée, le temps de traitement pour une gamme et une machine donnée, vecteur définissant l’ordre d’entrée des pièces dans le système, constantes contenant les autres données.

Le logiciel QNAP simplifie la programmation en implémentant des stations (file d’attente + machine) pouvant faire office de source (entrée des pièces) ou de serveur (machine à proprement parler).

Notre problème nécessitant un ordre des pièces en entrée, la source ne sera pas une vraie source mais un serveur faisant entrer les pièces une à une dans le système lorsque cela est possible.

Nous considérerons pour le système trois hypothèses concernant les files d’attente en amont des machines.

• Hypothèse 1 : Les files d’attente sont de capacité infinie

• Hypothèse 2 : Les files d’attente sont de capacité finie (égal à 2)

• Hypothèse 3 : Il n’y a pas de file d’attente

L’hypothèse 1 ne demande aucun traitement supplémentaire à réaliser sur le logiciel QNAP. En effet, le logiciel considère que par défaut les files d’attente en amont des machines existent, ont une politique de gestion FIFO et sont de capacité infinie.

Les hypothèses 2 et 3 demandent l’utilisation de sémaphores. Un sémaphore agit comme un compteur de places disponibles dans une station.

Le principe est le suivant :

A chaque fois qu’une pièce souhaite accéder à une station, le programme demande à cette station si une place est disponible, si elle l’est, la pièce transite vers la station, si elle ne l’est pas, la pièce attend qu’une place se libère. Il s’agit de l’opération P(sémaphore).

A chaque fois qu’une pièce a quitté une station, le programme libère une place sur la station que la pièce vient de quitter. Il s’agit de l’opération V(sémaphore).

2 Principe :

Gestion de la source :

Comme noté précédemment, la source agit comme un serveur afin de pouvoir ordonnancer les pièces.

L’option INIT = 1, permet d’assurer que la présence d’un seul client sur ce pseudo-serveur, client qui sera libérer (TRANSIT(OUT)) lorsque toutes les pièces seront entrées dans le système.

C’est la source qui va créer les clients d’où la nécessité d’un pointeur sur un client, pour chaque client que cette source doit faire entrer, nous initialisons son numéro, sa gamme, son numéro d’opération courante.

Puis nous dirigeons cette pièce vers la bonne machine selon son numéro de gamme.

Gestion d’une station :

Le service d’une station est gérée comme ci-après :

Mise à jour du numéro de l’opération courante de la pièce ;

Traitement de la pièce pendant la durée correspondant à sa gamme ;

Si la pièce est passée sur toutes les machines alors

Mise à jour du makespan (date de sortie de la dernière pièce) ;

...