Nos travaux de recherche portent sur le problème de prise en compte des contraintes liées aux ressources humaines, en termes d'affectation des opérateurs aux machines, dans les problèmes d'ordonnancement d'atelier. Ce problème intégrant l'affectation des opérateurs aux machines consiste à déterminer 1 'état d'atelier au cours du temps, et à considérer le problème d'ordonnancement d'atelier dans sa globalité en prenant en compte l'influence de l'affectation des ressources humaines sur les activités de production. Ceci impose en plus de la gestion de la séquence des travaux, la gestion des affectations des hommes aux postes de travail. Nous avons considéré le cas où les productivités des machines dépendant de 1 'affectation des opérateurs. Nous avons supposé que le nombre d'opérateurs est inférieur au nombre de machines, un opérateur peut superviser simultanément plusieurs machines et que la supervision simultanée de plusieurs machines par un opérateur diminue les productivités de ces dernières. L'originalité de nos travaux de recherche est liée au fait que les durées opératoires des travaux sont variables dans le temps et sont fonctions de 1 'évolution des affectations des opérateurs aux machines dans le temps. Deux grandes parties composent nos travaux de recherche. La première partie porte sur le problème de modélisation de 1 'affectation des opérateurs aux machines. Elle consiste en la proposition d'un cadre théorique pour 1 'intégration des contraintes liées à la prise en compte des ressources humaines, en terme d'affectation des opérateurs aux machines, dans la modélisation des problèmes d'ordonnancement d'atelier. Une définition d'un problème d'ordonnancement d'atelier impliquant l'aspect" ressources humaines" est alors proposée. La seconde partie a porté sur une application de la modélisation proposée dans la première partie pour le cas d'une production cyclique. Plus précisément, nous avons étudié le problème d'existence d'une affectation des opérateurs réalisant un ordonnancement cyclique pour un atelier_ de type Flow Shop. Nous avons supposé qu'un ordonnancement cyclique, défini par une durée de cycle et un ensemble de travaux à réaliser durant cette durée, est donné pour des productivités nominales des machines et sans aucune prise en compte des ressources humaines. Par conséquent, et dans le cas où le nombre d'opérateurs est inférieur au nombre de machines et que l'affectation des opérateurs conditionnent les productivités des machines, 1 'introduction et la considération des ressources humaines pour la réalisation de l'ordonnancement cyclique pourrait allonger la durée d'exécution des travaux et remettre en cause la durée de cycle. Nous avons étudié ce problème d'existence d'une affectation des opérateurs réalisable pour Flow Shop Cyclique pour trois modes de réaffectations des opérateurs : calendaire, sur évènement de fin de tâche et libre. Nous avons présenté une formulation mathématique du problème pour ces trois modes de réaffectation des opérateurs, démontré que ce problème est NP-complet pour les deux modes calendaires et sur événement, et qu'une restriction du problème de mode de réaffectation libre est NP-complet. Nous avons également proposé, pour ces trois modes, un modèle mathématique linéaire en nombre entier. Une approche de résolution basée sur le principe de la programmation dynamique a été proposée pour les deux modes réaffectation calendaire et sur événement.

Au cours de ces dernières années, les problèmes d'ordonnancement flexible ont largement attiré l'attention des chercheurs dans le domaine de la recherche opérationnelle. Ces problèmes présentent une difficulté supplémentaire du fait qu'une opération peut être exécutée par une ou plusieurs ressources devant être choisie(s) parmi d'autres candidates. L'objectif étant alors d'affecter et de séquencer les opérations sur les ressources en minimisant la durée d'exécution totale ou makespan. Dans cette étude, nous proposons de résoudre trois types de problèmes d'ordonnancement flexible : le flow shop hybride à plusieurs étages, à deux étages et le job shop flexible, en utilisant les méthodes arborescentes à base de divergences. Une étude expérimentale exhaustive a prouvé l'efficacité des différentes approches proposées pour les différents types de problèmes.

本研究開發一個以區域最佳解為基礎的群體式 (population-based) 啟發式演算法(簡稱HLBS)，來求解流程式排程（flow shop）之最大流程時間的最小化問題。其中，HLBS會先建置一個跟隨模型來導引搜尋機制，然後，運用過濾策略來預防重複搜尋相同解空間而陷入區域最佳解的困境；但搜尋仍有可能會陷入區域最佳解，這時，HLBS則會啟動跳脫策略來協助跳出區域最佳解，以進入新的區域之搜尋；為驗證HLBS演算法的績效，本研究利用著名的Taillard 測試題庫來進行評估，除證明跟隨模型、過濾策略和跳脫策略的效用外，也提出實驗結果證明HLBS較其他知名群體式啟發式演算法(如基因演算法、蟻群演算法以及粒子群最佳化演算法)之效能為優。 / This research proposes population-based metaheuristic based on the local best solution (HLBS) for the permutation flow shop scheduling problem (PFSP-makespan). The proposed metaheuristic operates through three mechanisms: (i) it introduces a new method to produce a trace-model for guiding the search, (ii) it applies a new filter strategy to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima, and (iii) it initiates a new jump strategy to help the search escape if the search does become trapped at a local optimum. Computational experiments on the well-known Taillard's benchmark data sets will be performed to evaluate the effects of the trace-model generating rule, the filter strategy, and the jump strategy on the performance of HLBS, and to compare the performance of HLBS with all the promising population-based metaheuristics related to Genetic Algorithms (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO).

La première partie de ce travail concerne la production cyclique pour l'optimisation du taux de production dans les flowshops robotisés, où un robot est chargé du transport des pièces. Les cellules robotisées peuvent être disposées de façon linéaire ou circulaire. Les principaux résultats théoriques concernant la disposition linéaire ne peuvent être étendus à la configuration circulaire. En particulier, trouver le meilleur cycle de production de une pièce (1-cycle) est un problème polynomial dans le cas des cellules linéaires additives, mais NP-difficile pour la configuration correspondante circulaire.Nous nous concentrons principalement sur le cas des cellules circulaires équilibrées, où le temps d'usinage est identique sur toutes les machines. Après avoir présentés des outils pour l'analyse cyclique dans les cellules circulaires, nous établissons des propriétés nécessaires des 1-cycles performants, ce qui permet de conclure sur le problème du meilleur 1-cycle jusqu'à 8 machines. Toutefois, nous fournissons un contre-exemple pour 6 machines à la conjecture classique des 1-cycles, toujours ouverte dans cette configuration.Ensuite, nous étudions la structure des 1-cycles performants pour des cellules circulaires équilibrées arbitrairement grandes. Nous définissons et étudions les propriétés d'une nouvelle famille de cycles basée sur cette structure et formulons une conjecture sur sa dominance sur les 1-cycles qui conduirait à un algorithme polynomial pour le problème du meilleur 1-cycle dans ce cas. Cette structure permet de déterminer le meilleur 1-cycle jusqu'à 11 machines.Dans la deuxième partie, nous présentons le travail réalisé sur un problème industriel proposé par la SNCF dans le cadre du challenge ROADEF/EURO. Nous proposons un algorithme glouton pour ce problème combinant divers aspects de la gestion des trains au sein d'une gare. / The first part of this work deals with cyclic production for throughput optimization in robotic flow-shops, where a robot is in charge of the material handling of parts. Robotic cells may have a linear or a circular layout. Most theoretical results for the linear layout do not hold for the circular layout. In particular, the problem of finding the best one part production cycle (1-cycle), which is a polynomial problem for linear additive cells, has been proved NP-hard for the corresponding circular configuration.We mainly focus on a special case of circular balanced cells, where the processing times are identical for all machines. After presenting tools for cyclic analysis in circular cells, we study necessary properties of efficient 1-cycles. These results allow to conclude on the best one part production cycle for any parameters in circular balanced cells up to 8 machines. However, we provide a counter-example to the classical 1-cycle conjecture, still open for this configuration.Then, we study the structure of efficient one part production cycles in arbitrarily large circular balanced cells. We introduce and study a new family of cycles based on this structure, and formulate a conjecture on its dominance over one part-production cycles, which would lead to a polynomial algorithm for finding the best 1-cycle for circular balanced cells. This structure allows to settle the best one part production cycle for cells with up to 11 machines.In a second part, we present work on an industrial problem of railway stock scheduling proposed by the French railway company in the context of the ROADEF/EURO competition. We propose a greedy algorithm for this problem combining the various aspects of trains handling inside a station.

Only if humanity acts quickly and resolutely can we limit global warming' conclude more than 25,000 academics with the statement of SCIENTISTS FOR FUTURE. The concern about global warming and the extinction of species has steadily increased in recent years.

[pt] Esta dissertação de mestrado analisa um problema de programação de máquinas em série com datas de entrega e ganhos cumulativos sob incerteza. Em particular, este trabalho considera situações reais na quais os tempos de processamento e datas de liberação são estocásticos. O objetivo principal deste trabalho é a resolução deste problema de programação de máquinas em série em um ambiente estocástico buscando analisar a relação entre diferentes niveis de incerteza e o benefício esperado. Visando atingir este objetivo, primeiramente uma heurística é proposta utilizando-se da técnica de biased-randomization para a versão determinística do problema. Então, esta heurística é extendida para uma metaheurística a partir do encapsulamento dentro da estrutura de um variable neighborhood descend. Finalmente, a metaheurística é extendida para uma simheurística a partir da incorporação da simulação de Monte Carlo. De acordo com os experimentos computacionais, o nível de incerteza tem um impacto direto nas soluções geradas pela simheurística. Além disso, análise de risco foram desenvolvidas utilizando as conhecidas métricas de risco: value at risk e conditional value at risk. / [en] This master s thesis analyzes the Permutation Flow-shop Scheduling Problem with Delivery Dates and Cumulative Payoffs under uncertainty conditions. In particular, the work considers the realistic situation in which processing times and release dates are stochastics. The main goal is to solve this Permutation Flow-shop problem in the stochastic environment and analyze the relationship between different levels of uncertainty and the expected payoff. In order to achieve this goal, first a biased-randomized heuristic is proposed for the deterministic version of the problem. Then, this heuristic is extended into a metaheuristic by encapsulating it into a variable neighborhood descent framework. Finally, the metaheuristic is extended into a simheuristic by incorporating Monte Carlo simulation. According to the computational experiments, the level of uncertainty has a direct impact on the solutions provided by the simheuristic. Moreover, a risk analysis is performed using two well-known metrics: the value at risk and the conditional value at risk.

Olofsfors is a steel product manufacturer in Nordmaling, Sweden, producing steel edges for snowplows, tracks for forest machines, and wear edges for buckets on heavy equipment. Most of their products are heated to 900◦ C and then cooled down in water, so-called quenching, during the hardening process. A group of ovens and quench machines together form an oven system and this is used for the hardening. Since it takes a long time for the ovens to reach operating temperature, they are always kept on, which is why it is important to utilize them as effectively as possible. This project investigates the potential utilization increase of one of the three oven systems in the wear edge production unit. This oven system is part of a production line that consists of a saw and a mill, and can process products up to two meters in length, and is hereon called the two-meter line. The two-meter line has a natural inflow through the saw, but raw material produced in other parts of the factory can also be fetched from another inlet. The use of the other inlet is limited by the operator of the two-meter line who has to fetch the material with a forklift. This could be automated so that the operator would not have to handle this inlet. The purpose is to investigate the potential increases in utilization of the oven system for different degrees of automation in order to make the most of the machines and the operator at the two-meter line. In the end, a recommendation is given with a set of ideal properties of the investment that could improve productivity the most. The main method applied in order to explore the potential use of the oven system is a re-entrant flow shop scheduling model. As preceding steps, the production line is first mapped in order to find potential routes for different product families, then the order quantities in the production data are translated into jobs to be scheduled with the help of packing problems and batching rules. The scheduling model of the production line is then solved heuristically with a genetic algorithm based on the sequence of jobs entering the production line followed by a method for creating a deterministic schedule based on this initial sequence of jobs. Lastly, a sensitivity analysis is applied to the processing time for the steps performed by the operator to evaluate the results' robustness. The conclusion is that there is a substantial potential to increase the utilization of the oven system of the two-meter line. The largest potential is when the operator is not actively working at the production line; a maximum of 15.6 h on average. There does also exist a potential to increase utilization while the operator is working at the production line; a maximum of 3.9 h on average. The automation degree needed is high in both cases but due to different reasons. When the operator is not working, the automatic solution needs to work without supervision for longer periods of time, while, in the other case, it needs to be smart enough to adjust to not disturb the operator’s work. For the future, the recommendation is to focus the next step on finding investment options that could exploit the time when the operator is not working. By further specifying the potential investment alternatives, the cost factor can be added to the analysis as well. / Olofsfors AB är en stålproduktstillverkare i Nordmaling, Sverige, som producerar vägstål till bland annat snöplogar, band till skogsmaskiner och slitstål till entreprenadmaskiner. De flesta av deras produkter hettas upp till 900 C och släcks sedan i vatten under härdningsprocessen. En grupp av ugnar och härdmaskiner kallas tillsammans för ett ungsystem och det används till härdningen. Eftersom det tar lång tid att värma upp ugnarna står de alltid på-slagna och det är därför viktigt att använda dem så effektivt som möjligt.  I detta projekt har potentialen att öka användandet av ett av tre ugnsystem i slitstålsproduktionen undersökts.  Ugnsystemet i fråga är en del av en produktionslinje som också består av en såg och en fräs och kan härda artiklar med längder upp till två meter och kallas därför här tvåmeterslinjen. Den naturliga ingången för råmaterial i produktionslinjen är genom sågen, men det finns även en alternativ ingång för råmaterial som förbehandlats i tidigare produktionssteg i fabriken. Användandet av den andra ingången till produktionlinjen begränsas av att operatören i produktionslinjen måste hämta materialet med truck. Detta in-flöde skulle gå att automatisera så att operatören inte skulle behöva hämta dessa artiklar.  Syftet är att undersöka det potentiella ökade nyttjandet av ugnsystemet för olika grader av automation för att bäst använda maskiner och operatör i tvåmeterslinjen. I slutet ges en rekommendation gällande vilka egenskaper investeringen bör ha för att öka produktiviteten mest.  Huvudmetoden för att undersöka möjligt ökat nyttjande av ugnarna är en schemaläggningsmodel. Som underliggande steg kartläggs först produktionslinjen och de olika rutter som olika produktfamiljer tar genom produktionslinjen. Produktkvantiteterna för varje order i produktionsdatan omvandlas sedan till jobb som kan schemaläggas genom packningsproblem och regler för laststorlekar i de olika maskinerna. Schemaläggningsmodellen löses sedan heuristiskt med hjälp av en genetisk algoritm som bestämmer den initiala sekvensen av jobben i första steget, tillsammans med en deterministisk metod för att skapa ett helt schema baserat på den initiala sekvensen av jobben. Slutligen genomförs en känslighetsanalys på processtiderna för steg som motsvarar operatören för att undersöka hur robust resultatet är.    Slutsatsen är att det finns en stor potential att öka nyttjandet av ugnsystemet i tvåmeterslinjen. Den största potentialen är när operatören inte arbetar aktivt vid produktionslinjen, med ett maximum på ca 15,6 h per dag. Det finns också en möjlighet att utöka nyttjandet av ugnarna under tiden som operatören arbetar aktivt med ordrar och outnyttjad tid då är 3,9 h i genomsnitt. Graden av automation är hög oberoende av vilken tid som ska utnyttjas men på grund av olika anledning. Om tiden då operatören inte aktivt jobbar utnyttjas, måste den automatiserade lösningen fungera autonomt under längre tid. Om den istället förväntas fungera parallellt med operatören måste den anpassas smart så att den inte stör operatörens arbete och flöde. Rekommendationen är att fokusera på att hitta konkreta investeringsalternativ som utnyttjar tiden då operatören inte aktivt arbetar för att få bättre kostnadsunderlag att ha med i den vidare analysen.

Pour la résolution de problèmes d’ordonnancement d’ateliers de type flow-shop en industries pharmaceutiques et d’ateliers de type job-shop flexible, deux méthodes d’optimisation ont été développées : une méthode utilisant les algorithmes génétiques dotés d’un nouveau codage proposé et une méthode d’optimisation par essaim particulaire modifiée pour être exploitée dans le cas discret. Les critères retenus dans le cas de lignes de conditionnement considérées sont la minimisation des coûts de production ainsi que des coûts de non utilisation des machines pour les problèmes multi-objectifs relatifs aux industries pharmaceutiques et la minimisation du Makespan pour les problèmes mono-objectif des ateliers job-shop flexibles.Ces méthodes ont été appliquées à divers exemples d’ateliers de complexités distinctes pour illustrer leur mise en œuvre. L’étude comparative des résultats ainsi obtenus a montré que la méthode basée sur l’optimisation par essaim particulaire est plus efficace que celle des algorithmes génétiques, en termes de rapidité de la convergence et de l’approche de la solution optimale / For flexible job-shop and pharmaceutical flow-shop scheduling problems resolution, two optimization methods are considered: a genetic algorithm one using a new proposed coding and a particle swarm optimization one modified in order to be used in discrete cases.The criteria retained for the considered packaging lines in pharmaceutical industries multi-objective problems are production cost minimization and total stopping cost minimization. For the flexible job-shop scheduling problems treated, the criterion taken into account is Makespan minimization.These two methods have been applied to various work-shops with distinct complexities to show their efficiency.After comparison of these methods, the obtained results allowed us to notice the efficiency of the based particle swarm optimization method in terms of convergence and reaching optimal solution

Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces. / In this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature.

No description available.