The flow shop scheduling problems with fuzzy processing times and fuzzy due dates are investigated in this paper. The concepts of earliness and tardiness are interpreted by using the concepts of possibility and necessity measures that were developed in fuzzy sets theory. And the objective function will be taken into account through the different combinations of possibility and necessity measures. The genetic algorithm will be invoked to tackle these objective functions. A new idea based on longest common substring will be introduced at the best-keeping step. This new algorithm reduces the number of generations needed to reach the stopping criterion. Also, we implement the algorithm on CUDA. The numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU.

Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.

Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.

Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.

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.

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.

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

A CONWIP (Constant Work-In-Progress) system is basically a hybrid system with a PUSH-PULL interface at the first machine in the line. This research addresses the most general case of a cyclic CONWIP system by incorporating two additional constraints over earlier studies namely; stochastic processing times and limited intermediate storage. One of the main issues in the design of a CONWIP system is the WIP level 'M', to be maintained. This research proposes an iterative procedure to determine this optimal level. The second main issue is the optimization of the line by determining an appropriate job sequence. This research assumes a 'permutational' scheduling policy and proposes an iterative approach to find the best sequence. The approach utilizes a controlled enumerative approach called the Fast Insertion Heuristic (FIH) coupled with a method to appraise the quality of every enumeration at each iteration. This is done by using a modified version of the Floyd's algorithm, to determine the cycle time (or Flow time) of a partial/full solution. The performance measures considered are the Flow time and the Interdeparture time (inverse of throughput). Finally, both the methods suggested for the two subproblems, are tested through computer implementations to reveal their proficiency. / Master of Science

近年來，印刷電路板(printed circuit board, PCB)產業在台灣蓬勃發展，對台灣經濟表現有相當重要的影響；與此同時，產業內各廠商卻因內外環境變異等因素，而面臨日益激烈的競爭壓力。本研究針對產業前段的生產工廠(PCB manufacturing)從管理面探討問題來源，發現各廠商所導入的管理系統(MRP、ERP、SCM等)均缺乏現場排程(shop floor scheduling)功能，因此造成排程結果不具可行性，連帶導致管理系統的績效也未如預期理想。 　　為解決該產業所面臨的現場排程問題，本研究透過個案訪談方式，對產業特性深入了解，歸類此類問題為排程領域中的流程型工廠排程問題(flow shop scheduling)。 　　在求解過程中，本研究以總延遲時間(total tardiness)最小化為目標，並以禁忌搜尋法(tabu search)作為最佳化過程的演算法。於理論探討後，本研究亦實際建置一套排程系統，並以來自個案工廠的訂單資料實際求解，以評估此系統績效。