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.

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.