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.

Os processos industriais de produção exigem uma programação da produção efetiva. Essa atividade consiste da alocação dos recursos produtivos, a fim de executar tarefas determinadas por um período de tempo definido. Programar a produção é uma das atividades mais complexas do Planejamento da Produção, pois existem diferentes tipos de recursos a serem administrados simultaneamente. E também a quantidade de possíveis soluções aumenta exponencialmente com o aumento da quantidade de tarefas e máquinas presentes no sistema. A proposta deste trabalho é apresentar um método heurístico construtivo para a solução de problemas flow shop permutacional. A função-objetivo utilizada é a minimização do tempo total da programação (makespan). O algoritmo foi desenvolvido com base no melhor algoritmo construtivo presente na literatura, e os resultados obtidos são discutidos e analisados com base na porcentagem de sucesso, desvio relativo médio e tempo médio de computação. / Industrial productive processes demand an effective production scheduling. These activities consist in allocating the productive resources in order to execute determined jobs for a established period of time. Scheduling the production is one of the most complex activities involved in Planning the Production because there are different kinds of resources to be managed simultaneously. Furthermore, the amounts of feasible solutions increase exponentially as the number of jobs and machines in large systems. This dissertation presents a constructive heuristic method to solve the permutational flow shop problem. The evaluation criterion is the total production elapsed time (makespan). The developed algorithm was based on the best algorithm found in the literature, the results are analysed based on the success rate, mean relative deviation and computing time.

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.

本研究開發一個以區域最佳解為基礎的群體式 (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).

[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.

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>