Over the last decade, the semiconductor industry has witnessed a steady increase in its complexity based on improvements in manufacturing processes and equipment. Progress in the technology used is no longer the key to success, however. In fact, the semiconductor technology has reached such a high level of complexity that improvements appear at a slow pace. Moreover, the diffusion of technology among competitors shows that traditional approaches based on technological advances and innovations are not sufficient to remain competitive. A recent crisis in the semiconductor field in the summer 2001 made it even clearer that optimizing the operational control of semiconductor wafer fabrication facilities is a vital key to success. Operating research-oriented studies have been carried out to this end for the last 5 years. None of them, however, suggest a comprehensive model and solution to the operational control problem of a semiconductor manufacturing facility. Two main approaches, namely mathematical programming and dispatching rules, have been explored in the literature so far, either partially or entirely dealing with this problem. Adapting the Shifting Bottleneck (SB) procedure is a third approach that has motivated many studies. Most research focuses on optimizing a certain objective function under idealized conditions and thus does not take into consideration system disruptions such as machine breakdown. While many papers address the adaptations of the SB procedure, the problem of re-scheduling jobs dynamically to take disruptions and local disturbances (machines breakdown, maintenance...) into consideration shows interesting perspectives for research. Dealing with local disturbances in a production environment and analyzing their impact on scheduling policies is a complex issue. It becomes even more complex in the semiconductor industry because of the numerous inherent constraints to take into account. The problem that is addressed in this thesis consists of studying dynamic scheduling in a job-shop environment where local disturbances occur. This research focuses on scheduling a large job shop and developing re-scheduling policies when local disturbances occur. The re-scheduling can be applied to the whole production horizon considered in the instance, or applied to a restricted period T that becomes a decision variable of the problem. The length of the restricted horizon T of re-scheduling can influence significantly the overall results. Its impact on the general performance is studied. Future extensions can be made to include constraints that arise in the semiconductors industry, such as the presence of parallel and batching machines, reentrant flows and the lot dedication problem. The theoretical results developed through this research will be applied to data sets to study their efficiency. We hope this methodology will bring useful insights to dealing effectively with local disturbances in production environments. / Master of Science

Nos travaux concernent l’étude d’une extension d’un problème d’ordonnancement bien connu sous l’appellation job shop. Nous appelons cette extension le General Flexible Job Shop Scheduling Problem (GFJSSP). Celui-ci se rencontre dans différents types d’ateliers ayant comme caractéristique commune d’être soumis à des contraintes dues à des ressources de transport. Le GFJSSP se caractérise par l’intégration de machines et robots flexibles. Le terme General induit par ailleurs la présence de robots dont la capacité est supposée unitaire dans notre étude, des temps opératoires bornés, et la possibilité de prise en compte d’emplacements de stockage spécifiques. Après avoir défini l’atelier et le problème correspondant à cette extension, nous avons proposé deux modélisations du GFJSSP ainsi défini : une première modélisation mathématique linéaire, et une modélisation graphique, qui correspond à une généralisation du graphe disjonctif couramment utilisé pour les problèmes de job shop. Nous avons ensuite abordé la résolution suivant deux étapes : tout d’abord en nous focalisant sur l’aspect séquencement des tâches de traitement et de transport, pour lequel nous avons élaboré deux méthodes heuristiques (de type Tabou et basée sur une procédure de shifting bottleneck améliorée) ; puis en intégrant dans un deuxième temps la problématique de l’affectation induite par la flexibilité de certaines ressources. Pour cette dernière étape, nous avons combiné les méthodes précédentes avec un algorithme génétique. L’algorithme hybride obtenu nous permet de résoudre des instances de la littérature correspondant à divers cas spécifiques, avec des résultats assez proches des meilleures méthodes dédiées. A termes, il pourrait être intégré dans un système d'aide à la décision général qui s’affranchirait de la phase d’identification préalable du type de job shop considéré, et serait adapté à la résolution de nombreux cas (avec ou sans problème d'affectation, temps de traitement fixes ou bornés, avec ou sans stockage, etc..). / Our work focuses on an extension of the well known job shop scheduling problem. We call this extension the General Flexible Job Shop Scheduling Problem (GFJSSP). It occurs in various kinds of workshops which are particularly constrained by one or several transportation resources (called robots). GFJSSP is characterized by the flexibility of both machines and robots. In the studied problem, the term General involves unitary capacity transportation resources, bounded processing times, and possible input/output buffers for machines. After defining the workshop and the corresponding problem, we proposed two kinds of model for the GFJSSP: a mathematical model, and a graphical one. This last one is a generalization of the disjunctive graph commonly used for job shop problems. We then addressed the resolution in two steps: firstly, by focusing on the sequencing of processing and transportation tasks. For this purpose we have developed two heuristics (Tabu search and an improved shifting bottleneck procedure). Secondly, we have considered the assignment problem involved by the flexibility of some resources. For this last step, we combined the above methods with a genetic algorithm. This hybrid algorithm allowed us to solve various specific cases of instances in the literature, with performance rather close to the best dedicated methods. In the future, it could be integrated within a general decision support system which could emancipate from the initial identification phase of the considered type of job shop, and which would be suitable for solving many cases (with or without assignment problem, fixed or bounded processing times, with or without storage, and so on).

The thesis work develops an automated, data-driven bottleneck detection procedure based on real-world data. Following a seven-step process it is possible to determine the average as well as the shifting bottleneck by automatically applying the active period method. A detailed explanation of how to pre-process the extracted data is presented which is a good guideline for other analysists to customize the available code according to their needs. The obtained results show a deviation between the expected bottleneck and the bottleneck calculated based on production data collected in one week of full production. The expected bottleneck is currently determined by the case company by measuring cycle times physically at the machine, but this procedure does not represent the whole picture of the production line and is therefore recommended to be replaced by the developed automated analysis. Based on the analysis results, different optimization potentials are elaborated and explained to improve the data quality as well as the overall production capacity of the investigated production line. Especially, the installed gantry systems need further analysis to decrease their impact on the overall capacity. As for data quality, especially, the improvement of the machines data itself as well as the standardization of timestamps should be focused to enable better analysis in the future. Finally, future recommendations mainly suggest to run the analysis several times with new data sets to validate the results and improve the overall understanding of the production lines behavior. / Detta examensarbete utvecklar en process för en automatiserad, datadriven flaskhalsidentifiering baserad på verkliga data. Följt av en sjustegsprocess ges det möjlighet att bestämma den genomsnittliga och den varierande flaskhalsen genom en automatisk implementering av ”the active period method”. En detaljerad förklaring av hur man förbehandlar informationen som extraherats är presenterat vilket är en god riktlinje för andra analytiker för att anpassa den tillgängliga koden utifrån deras behov. Det samlade resultatet illustrerar en avvikelse mellan den förväntade flaskhalsen och den flaskhalsen som utgår ifrån beräkningar av tillverkningsdata ansamlat i en vecka av full produktion. Den förväntade flaskhalsen är för nuvarande bestämt av fallets företag genom en fysisk mätning av cykeltiderna på maskinen, däremot är denna process inte representativ för helhetsbilden på tillverkningslinjen och det är därvid rekommenderat att ersätta den föregående flaskhalsidentifieringen med den utvecklade automatiserade analysen. Baserat på analysens resultat framkom det olika optimiseringsmöjligheter som är utvecklade och klargjorda för att förbättra kvaliteten på data samt den övergripande produktionskapaciteten av den undersökta produktionslinjen. Speciellt när det gällerde installerade portalsystemen så behövs det en fördjupande analys för att minimera dess verkan på den översiktliga kapaciteten. När det gäller datakvalitet, speciellt förbättringen av maskindata, behövs det en standardiserad tidsstämpling för att utföra enbättre analys i framtiden. De framtida rekommendationerna föreslår huvudsakligen att köra analysen ett flertal gånger med nya datauppsättningar för att validera resultaten och förbättra den övergripliga uppfattningen av produktionslinjens beteende.

Nos travaux concernent l'étude d'une extension d'un problème d'ordonnancement bien connu sous l'appellation job shop. Nous appelons cette extension le General Flexible Job Shop Scheduling Problem (GFJSSP). Celui-ci se rencontre dans différents types d'ateliers ayant comme caractéristique commune d'être soumis à des contraintes dues à des ressources de transport. Le GFJSSP se caractérise par l'intégration de machines et robots flexibles. Le terme General induit par ailleurs la présence de robots dont la capacité est supposée unitaire dans notre étude, des temps opératoires bornés, et la possibilité de prise en compte d'emplacements de stockage spécifiques. Après avoir défini l'atelier et le problème correspondant à cette extension, nous avons proposé deux modélisations du GFJSSP ainsi défini : une première modélisation mathématique linéaire, et une modélisation graphique, qui correspond à une généralisation du graphe disjonctif couramment utilisé pour les problèmes de job shop. Nous avons ensuite abordé la résolution suivant deux étapes : tout d'abord en nous focalisant sur l'aspect séquencement des tâches de traitement et de transport, pour lequel nous avons élaboré deux méthodes heuristiques (de type Tabou et basée sur une procédure de shifting bottleneck améliorée) ; puis en intégrant dans un deuxième temps la problématique de l'affectation induite par la flexibilité de certaines ressources. Pour cette dernière étape, nous avons combiné les méthodes précédentes avec un algorithme génétique. L'algorithme hybride obtenu nous permet de résoudre des instances de la littérature correspondant à divers cas spécifiques, avec des résultats assez proches des meilleures méthodes dédiées. A termes, il pourrait être intégré dans un système d'aide à la décision général qui s'affranchirait de la phase d'identification préalable du type de job shop considéré, et serait adapté à la résolution de nombreux cas (avec ou sans problème d'affectation, temps de traitement fixes ou bornés, avec ou sans stockage, etc..).

No description available.