Esta dissertação estuda o problema da programação de operações em sistemas job shop de manufatura onde itens com estruturas de materiais são produzidos a partir de componentes fabricados e montados. Tais sistemas são denominados assembly shops. O caso geral do problema de programação de operações em sistemas job shop, no qual não existem restrições quanto ao número de operações a serem programadas nem quanto ao número de máquinas a serem alocadas, é considerado, até o presente momento, intratável do ponto de vista computacional devido à explosão combinatória inerente ao processo de programação, independente da escolha do critério de desempenho. Isto significa dizer que não existe nenhum método eficiente de programação que resolva globalmente instâncias de porte real do problema dentro de um tempo computacional considerado satisfatório. Devido a este fato, nas últimas três décadas, diversos métodos aproximados e heurísticos foram propostos e avaliados para o problema. Nesta pesquisa, é proposto e avaliado um novo método heurístico de programação. Fundamentado na pressuposição de que a melhoria na sincronização de operações de montagem em sistemas assembly shop leva ao melhor atendimento de datas de entrega de pedidos, o método implementa duas abordagens de programação: uma abordagem backward que satisfaz completamente as datas de entrega e outra forward que satisfaz completamente a restrição de capacidade de máquina. Ambas trabalham iterativamente dentro de dois modelos de simulação do sistema de produção um determinístico e outro probabilístico na busca pela melhoria da sincronização das operações e no atendimento das datas de entrega. Os resultados experimentais demonstraram que o desempenho do novo método foi em média melhor que os dos métodos não iterativos (regras) avaliados e tão bom quanto o desempenho do melhor método não iterativo (regra) testado. / This dissertation studies the problem of scheduling operations in manufacturing job shop environments where items with bill of materials are made of many fabricated and assembled components. Such systems are known as assembly shops. The general job shop scheduling problem, which no restrictions exist neither for the number of operations to be scheduled nor for the number of machines to be allocated, is considered at the present date intractable from the computational point of view, whatever the performance criterion used, due to the combinatorial explosion inherent to the scheduling process. It means that there is not an efficient computational method that solves globally real size instances of the problem within a satisfactory period of time. Due to this fact, in the last three decades several approximated and heuristic methods were created and evaluated for the problem. This research proposes and evaluate a new heuristic method which is based on the assumption that the improvement in operations synchronization at the assembly stations brings forth better achievement of due dates. The method implements two scheduling approaches: a backward approach satisfying due date completely and a forward approach satisfying capacity restriction completely. The two approaches work iteratively within two different simulation models of the production system one deterministic e other probabilistic in searching for operations synchronization improvement and due date achievement. The experimental results have shown the new method was better than the single-pass methods (rules) on average and as good as the better single-pass method (rule) tested.

No description available.

Made available in DSpace on 2015-03-05T13:58:26Z (GMT). No. of bitstreams: 0 Previous issue date: 1 / Universidade do Vale do Rio dos Sinos / Neste trabalho é abordado o Problema de Escalonamento em um job shop, considerando restrições de datas de entrega, turnos de produção e tempo de setup entre operações. Considera-se um ambiente de Sistema de Manufatura flexível, que dado ao alto nível de automação, permite a previsibilidade dos processos de carregamento dos recursos à área de processamento. O problema foi modelado através de uma Função Objetivo fn composta de três variáveis de decisão. A importância da contribuição de cada variável para o valor de fn é gerida pela atribuição de valores aos pesos associados às variáveis. Na abordagem proposta, são utilizadas técnicas de Tecnologia de Grupo e Busca Tabu. O modelo implementado é uma modificação da técnica i TSAB, proposta por Nowicki e Smutnicki, a qual apresenta bons resultados no tratamento do Problema de Escalonamento em um job shop PEJS clássico. A consideração das restrições adicionais ao PEJS aumenta a complexidade do modelo implementado, porém, deixa o problema mais próximo da realidade. / In this work the Job Shop Scheduling Problem is studied, considering due dates, production turns and tooling constraints. This problem is applied in a Flexible Manufacturing System, which possesses high degree of automation, allowing previsibility in the processes of loading and unloading jobs on the machines. The problem is modeled through a objective function fn composed by three weighted decision variables. The importance of each variable in the fn final value is managed through assignment of values to the weights of these variables. In the proposed approach, it was used Group Technology and Tabu Search techniques. The implemented model is a modification of the i TSAB technique, proposed by Nowicki and Smutniki. The consideration of adicional constraints in the Job Shop Scheduling Problem increases the complexity of the implementation, otherwise, makes the problem closer to the industrial reality. The model was validated using benchmark instances, in which the data from the addional constraints were added.

Decentralized decision-making is an active research topic in artificial intelligence. In a distributed system, a number of individually acting agents coexist. If they strive to accomplish a common goal, the establishment of coordinated cooperation between the agents is of utmost importance. With this in mind, our focus is on multi-agent reinforcement learning (RL) methods which allow for automatically acquiring cooperative policies based solely on a specification of the desired joint behavior of the whole system.The decentralization of the control and observation of the system among independent agents, however, has a significant impact on problem complexity. Therefore, we address the intricacy of learning and acting in multi-agent systems by two complementary approaches.First, we identify a subclass of general decentralized decision-making problems that features regularities in the way the agents interact with one another. We show that the complexity of optimally solving a problem instance from this class is provably lower than solving a general one.Although a lower complexity class may be entered by sticking to certain subclasses of general multi-agent problems, the computational complexitymay be still so high that optimally solving it is infeasible. Hence, our second goal is to develop techniques capable of quickly obtaining approximate solutions in the vicinity of the optimum. To this end, we will develop and utilize various model-free reinforcement learning approaches.Many real-world applications are well-suited to be formulated in terms of spatially or functionally distributed entities. Job-shop scheduling represents one such application. We are going to interpret job-shop scheduling problems as distributed sequential decision-making problems, to employ the multi-agent RL algorithms we propose for solving such problems, and to evaluate the performance of our learning approaches in the scope of various established scheduling benchmark problems.

No description available.

Background: Optimal scheduling is a common practice in various industries, facili-tating efficient workflow management. Accelerating the generation of schedules while maintaining their optimality could encourage broader adoption of this approach inindustry settings. Previous work has aimed to estimate the makespan for the JobShop Scheduling Problem, showing promising results. Objectives: Given the increasing demand for AI and Machine Learning (ML) solutions across industries, this research aims to explore the integration of ML techniquesinto optimal scheduling processes. Specifically, the goal is to develop a faster scheduling solution without compromising the optimality of the generated schedules. The proposed approach combines the effectiveness and speed of ML with the optimal results obtained from mathematical scheduling models. Methods: This thesis focuses on the Job Shop Scheduling (JSS) Problem, where a mathematical scheduler is tasked with minimizing the makespan of a set of jobs while following a predefined set of rules. An initial investigation is performed to establish if there is potential in providing the scheduler with its optimal makespan to decrease the scheduling time. To generalize the application of the concept, the study investigates the potential efficiency acceleration achieved by providing the scheduler with a Machine Learning estimated makespan. This involves training a Neural Network(NN) to estimate the optimal makespan of job sets, which is then utilized to speedup the scheduling process. Results: The preliminary investigation demonstrates that providing the scheduler with the optimal makespan results in an average speed-up of schedule generationby 24%. The results of the scheduling time with the NN estimated makespan is on the other hand not as well performing. Despite achieving a level of accuracy in estimating the makespan, the resulting speed-up in the scheduler’s performance falls short. For the scheduler to benefit from being provided an estimated makespan it is therefore theorized to require a close-to-perfect estimation of the makespan, which was not achieved with the trained NN model. The trained NN reached an average accuracy of 95.75%. Conclusions: The study concludes that while ML models can accurately estimate makespan, the observed speed-up in scheduling performance is not as significant as anticipated. The correlation between well-estimated makespan and speed-up appearsto be inconsistent, indicating potential limitations in the current approach. Further investigation into the search algorithm employed by the scheduling tool Gurobi mayprovide insights into optimizing the scheduling process more effectively. In summary, while the integration of ML techniques shows promise in accelerating scheduling processes, a higher accuracy of the ML model would be required. Additional researchis needed to refine the approach and potentially bring a faster optimal scheduling solution into the future. / Bakgrund: Optimal schemaläggning är en vanlig implemetation inom flera olika branscher och underlättar hantering och effektiviserar arbetsflöden. Att påskynda genereringen av scheman samtidigt som den optimala aspekten av schemaläggning inte går till spillo, skulle kunna främja en bredare användning av optimal schemaläggning för fler brancher. Tidigare undersökningar har gjorts för att estimera "makespan" för Job Shop problemet inom schemaläggning och har visat lovande resultat. Syfte: Med den ökande efterfrågan på AI- och maskininlärnings lösningar inom olika branscher syftar denna forskning till att utforska integrationen av ML-tekniker i den optimala schemaläggningsprocessen. Målet är att utveckla en snabbare schemaläggningslösning utan att kompromissa med det genererade schemats optimalitet. Det föreslagna tillvägagångssättet kombinerar ML’s effektivitet och hastighet med de optimala resultaten som den matematiska schemaläggningsmodellen erbjuder. Metod: Forskningen fokuserar på problemet med schemaläggning för jobbshoppen(JSSP), där en matematisk schemaläggare har i uppgift att minimera makespan fören uppsättning jobb med hänsyn till ett par fördefinierade regler. En initial under-sökning görs, vilket visar att det finns potential i att tillhandahålla schemaläggarendess optimala makespan för att minska schemaläggningstiden. För att generalisera tillämpningen undersöker studien den potentiella accelerationen som uppnås genomatt tillhandahålla schemaläggaren ett maskininlärt uppskattat makespan. Detta medför att träna ett neuralt nätverk för att uppskatta det optimala makespanet för en mängd jobbuppsättningar, som sedan används för att påskynda schemaläggningsprocessen. Resultat: Den preliminära undersökningen visar att schemaläggaren resulterar i igenomsnittlig hastighetsökning av schemagenereringen med cirka 24% när den får tillgång till det optimala makespanet för de givna jobben. Resultaten av schemaläggningstiden med det neurala nätverkets uppskattade makespan är dock lägre än förväntat. Trots att en viss noggrannhetsnivå uppnås vid estimeringen av makespanet, når den resulterande hastighetsökningen i schemaläggarens prestanda inte upp tillförväntningarna. För att schemaläggaren ska dra nytta av att tillhandahålla ett uppskattad makespan krävs en nära perfekt uppskattning av makespan, vilket inte uppnåddes med det tränade neurala nätverket. Slutsatser: Studien drar slutsatsen att även om ML-modeller kan uppskatta makespan någorlunda noggrant, är den observerade hastighetsökningen i schemaläggningen inte lika betydande som förväntat. Korrelationen mellan väl uppskattad makespan och hastighetsökning verkar vara inkonsekvent, vilket indikerar potentiella begränsningar i det nuvarande tillvägagångssättet. Vidare undersökning av sökalgoritmen som används av schemaläggningsverktyget Gurobi kan ge insikter för att optimera schemaläggningsprocessen mer effektivt. Sammanfattningsvis visar integrationen av ML-tekniker lovande resultat för att accelerera schemaläggningsprocesser, men en bättre estimering av makespan skulle krävas. Ytterligare forskning behövs för att förbättra tillvägagångssättet och potentiellt introducera en snabbare optimal schemaläggningslösning för framtiden.

Growing concerns over global warming and increasing fuel costs have pushed the traditional fuel-based centralized electrical grid to the forefront of mounting public pressure. These concerns will only intensify in the future, owing to the growth in electricity demand. Such growths require increased generation of electricity to meet the demand, and this means more carbon footprint from the electrical grid. To meet the growing demand economically by using clean sources of energy, the electrical grid needs significant structural and operational changes to cope with various challenges. Microgrids (µGs) can be an answer to the structural requirement of the electrical grid. µGs integrate renewables and serve local needs, thereby, reducing line losses and improving resiliency. However, stochastic nature of electricity harvest from renewables makes its integration into the grid challenging. The time varying and intermittent<br>nature of renewables and consumer demand can be mitigated by the use of storages and dynamic load scheduling. Automated dynamic load scheduling constitutes the operational changes that could enable us to achieve energy efficiency in the grid.<br>The current research works on automated load scheduling primarily focuses on scheduling residential and commercial building loads, while the current research on manufacturing scheduling is based on static approaches with very scarce literature on job shop scheduling. However, residential, commercial and, industrial sector, each contribute to about one-third of the total electricity consumption. A few research<br>works have been done focusing on dynamic scheduling in manufacturing facilities for energy efficiency. In a smart grid scenario, consumers are coupled through electricity<br>pool and storage. Thus, this research investigates the problem of integrating production line loads with building loads for optimal scheduling to reduce the total electricity<br>cost in a µG.<br>This research focuses on integrating the different types of loads from different types of consumers using automated dynamic load scheduling framework for sequential decision making. After building a deterministic model to be used as a benchmark, dynamic load scheduling models are constructed. Firstly, an intelligent algorithm is developed for load scheduling from a consumer’s perspective. Secondly, load scheduling model is developed based on central grid controller’s perspective. And finally, a reinforcement learning model is developed for improved load scheduling by sharing<br>among multiple µGs. The performance of the algorithms is compared against different well-known individualistic strategies, static strategies and, optimal benchmark<br>solutions. The proposed dynamic load scheduling framework is model free with minimum assumptions and it outperforms the different well-known heuristics and static strategies while obtains solutions comparable to the optimal benchmark solution.<br>The future electrical grid is envisioned to be an interconnected network of µGs. In addition to the automated load scheduling in a µG, coordination among µGs by<br>demand and capacity sharing can also be used to mitigate stochastic nature of supply and demand in an electrical grid. In this research, demand and resource sharing<br>among µGs is proposed to leverage the interaction between the different µGs for developing load scheduling policy based on reinforcement learning. <br>

Nous présentons les enjeux du management environnemental et soulignons l’importance d’une politique d’économie d’énergie pour les entreprises. Nous proposons un modèle pour déterminer le bilan énergétique de la fabrication en intégrant les différentes phases productives et non-productives. Nous définissons un double objectif pour la minimisation de la durée de production et de la consommation d’énergie. Nous appliquons ce modèle à l’ordonnancement d’ateliers job-shop flexibles. Pour déterminer la solution optimale nous utilisons deux classes de méthodes : - La première relève des algorithmes génétiques. Nous proposons différents types d’algorithmes pour résoudre ce problème multicritère. Nous proposons par exemple de faire évoluer deux populations pour minimiser respectivement l’énergie consommée et la durée de production et de les croiser pour atteindre l’objectif global. - La seconde relève de la programmation sous contrainte. Nous proposons de rechercher la solution optimale en développant une double arborescence pour évaluer l’énergie consommée et la durée de production. Nous construisons notre algorithme en partant des tâches à réaliser sur les machines ou en partant des machines qui réaliseront les tâches. Nous discutons de la construction du front de Pareto pour l’obtention de la meilleure solution.Nous terminons en comparant les différentes approches et en discutant leur pertinence pour traiter des problèmes de différentes tailles. Nous proposons également plusieurs améliorations et quelques pistes pour de futures recherches. / We present the challenges of environmental management and underline the importance of an energy saving policy for companies. We propose a model to determine the energy balance of manufacturing by integrating the different productive and non-productive phases. We define two purposes for minimizing production time and energy consumption. We apply this model to the scheduling of flexible job-shop workshops. To determine the optimal solution we use two types of methods: - The first is genetic algorithms. We propose different types of algorithms to solve this multi-criteria problem. For example, we propose to develop two populations to minimize the energy consumed and the production time, and to cross them to achieve the overall objective. - The second is constraint programming. We propose to find the optimal solution by developing a double tree to evaluate the energy consumed and the production time. We build our algorithm starting from the tasks to be performed on the machines or from the machines that will perform the tasks. We discuss the construction of the Pareto front to get the best solution.We finish by comparing the different approaches and discussing their relevance to deal with problems of different sizes. We also offer several improvements and some leads for future research.

Scheduling in the context of manufacturing systems has become increasingly impor- tant in order for organizations to achieve success in dynamic and competitive scenarios. Scheduling can be described as allocation of available jobs over resources to meet the performance criteria defined in a domain. Our research work fo cuses on scheduling a given set of three-dimensional cylindrical items, each characterized by width wj , height hj, and depth dj , onto parallel non-identical rectangular heat treatment kilns, such that the capacities of the kilns is optimally used. The problem is strongly NP-hard as it generalizes the (one-dimensional) Bin Packing Problem (1BP), in which a set of n positive values wj has to be partitioned into the minimum number of subsets so that the total value in each subset does not exceed the bin capacity W. The problem has been formulated as a variant of the 3D-BPP by following the MILP approach, and we propose a weight optimization heuristic that produces solutions comparable to that of the LP problem, in addition to reducing the computational complexity. Finally, we also propose a Decomposition Algorithm (DA) and validate the perfor- mance effectiveness of our heuristic. The numerical analyses provides useful insights that influence the shop-floor decision making process.

Le management de la chaîne logistique concerne un large éventail d’activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l’incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l’incertitude, l’indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d’incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d’aborder ce problème d’une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l’incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d’incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L’incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décision / Supply chain management involves a wide range of activities. Among most of them, uncertainty exists inherently and always brings some consequence not expected. However, uncertainty is not considered much in conventional supply chain management. In the case where availability of resources is not what we expect, complexity of supply chain management increases. Taking constraints of uncertainty and availability into account, we aim to discuss supply chain management from different aspects. This thesis is an attempt of systematic and complete research from this point and we would like to offer some references to researchers and managers in supply chain. We focus on three classic sources of uncertainty: demand, manufacturing and distribution. For each source of uncertainty, we analyze its cause and its impact to the performance of the supply chain. Uncertainty is specified into concrete classic problem and an approach is proposed to solve it. Furthermore, bi-level newsboy problem as a miniature of supply chain, is focused under double uncertain environment. Treating uncertain variables is actually a treatment on operational level. The methods used offer good demonstration in treating uncertain variables in decision problems