Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-06-22T16:10:58Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertacao_SinndyDayanaRicoLugo_2016.pdf: 3067162 bytes, checksum: bf4e6bc8fdefc54a21c8315582de00a1 (MD5) / Made available in DSpace on 2016-06-22T16:10:58Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertacao_SinndyDayanaRicoLugo_2016.pdf: 3067162 bytes, checksum: bf4e6bc8fdefc54a21c8315582de00a1 (MD5) Previous issue date: 2016-02-01 / CNPQ / A determinação dos requerimentos de materiais nas Pequenas e Médias Empresas (PMEs) cujo ambiente de produção é do tipo Job Shop, tem sido categorizado na literatura como um problema devido ao complexo processo de tomada de decisões subjacente, gerado pela grande quantidade de variáveis no sistema de fabricação, aos níveis de apropriação de tecnologias da informação e às características dos modelos e das ferramentas que atualmente encontram-se disponíveis. Dentro deste contexto, uma solução fundamentada em um modelo de decisão multicritério foi proposta, incluindo a execução do processo de elicitação das preferências do decisor, e suportada na geração de um Sistema de Apoio à Decisão (SAD) de ambiente Web. Ao longo deste trabalho é apresentada a caracterização das etapas de construção do modelo, os pontos relevantes para a escolha do Modelo Aditivo como base, as melhorias feitas ao processo de elicitação, e o detalhamento da interação do software desenvolvido com o processo decisório de determinação de requerimentos de matérias primas. Apresenta-se também a aplicação do modelo em algumas empresas do tipo PME, realizando uma análise comparativa entre os resultados esperados e os obtidos com o uso da ferramenta SAD e recolhendo todos os comentários dos decisores, com a finalidade de caracterizar, em um ambiente de fábrica real, os prós, contras e possíveis melhorias do modelo proposto. Todas as aplicações foram realizadas em duas fases: na primeira o decisor usou o SAD de forma isolada, sem o acompanhamento da analista com o intuito de obter uma visão totalmente externa; e na segunda o decisor usou o software com o acompanhamento direto da analista tendo como objetivo a interatividade e a troca de conhecimentos. A execução da primeira fase proporcionou informação relevante de como os decisores se sentem em relação às perguntas da elicitação de preferências, à linguagem usada, aos gráficos e às demais características desenvolvidas no aplicativo, concluindo que não contar com um analista obriga ao decisor a pensar cuidadosamente nas suas respostas e a ler detalhadamente as instruções. A segunda fase permitiu aos decisores maior compreensão do processo de elicitação e principalmente, em relação ao uso do SAD na etapa da analise de sensibilidade. Adicionalmente, apresenta-se a proposta de um segundo modelo baseado em outras teorias de decisão multicritério, Teoria de Utilidade Multiatributo (MAUT por sua sigla em inglês) e Utilidade Rank Dependente (RDU por sua sigla em inglês), com a diferença de que a ferramenta SAD foi testada com dados reais de única empresa. Assim, os resultados da aplicação deste modelo mostram diferenças substanciais entre utilizar o método clássico da Utilidade Esperada (EU em inglês) e usar a RDU; enquanto que diferenças menores, mas também relevantes, foram encontradas entre elicitar a função peso da probabilidade e usar os valores dos parâmetros sugeridos comumente na literatura com base em estudos comportamentais / Determining the requirements of materials in Small and Medium Enterprises (SMEs), whose production environment is Job Shop type, has been categorized in the literature as a problem caused by the complex underlying decision-making process, generated by the large number of variables in the manufacturing system, the appropriation levels of information technology and the characteristics of the models and tools that currently are available. Within this framework, a solution based on a multi-criteria decision model was proposed, including the execution of the elicitation process of decision maker's preferences, and supported in the generation of a decision support system (DSS) Web based. Throughout this document presents the characterization of model building steps, relevant points for choosing the Additive Model as a base, improvements made to the elicitation process and details of interaction within the software developed and the decision-making process of raw material requirements determination. It presents also the application of the model in some companies of type SME, performing a comparative analysis between expected results and those obtained using the SAD tool and compiling all the comments of decision-makers, in order to characterize, in environment real factory, the pros, cons and possible improvements of the proposed model. All applications were done in two phases: first the decision maker used the SAD in isolation, without the accompaniment of the analyst in order to get a fully external view; and in the second the decision maker used the software with analyst's direct monitoring aiming to the interaction and exchange of knowledge. The implementation of the first phase provided relevant information about how the decision-makers feel in relation to the preferences elicitation questions, to the language used, to the graphics and to other features developed in the application, concluding that if there is not an analyst, the decision maker has to think carefully in their responses and thoroughly reads the instructions. The second phase offered to decision-makers greater understanding of the elicitation process and especially regarding the use of the SAD in the sensitivity analysis step. In addition, a second model based on other theories of multi-criteria decision (Multi-attribute Utility Theory (MAUT) and Rank Dependent Utility (RDU)) was presented, with the difference that the SAD tool was tested with real data of only one company. Thus, the results of applying this model show substantial differences between using the classic method of Expected Utility (EU) and use RDU; while minor differences, but also relevant, were found between eliciting the probability weighting function and using the values of the parameters commonly suggested in the literature based on behavioral studies.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2018-05-25T13:02:54Z No. of bitstreams: 1 guilhermedesouzaferreira.pdf: 1163831 bytes, checksum: ec0bec904b2e6110d9b9e4934727f35d (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-06-14T11:52:03Z (GMT) No. of bitstreams: 1 guilhermedesouzaferreira.pdf: 1163831 bytes, checksum: ec0bec904b2e6110d9b9e4934727f35d (MD5) / Made available in DSpace on 2018-06-14T11:52:03Z (GMT). No. of bitstreams: 1 guilhermedesouzaferreira.pdf: 1163831 bytes, checksum: ec0bec904b2e6110d9b9e4934727f35d (MD5) Previous issue date: 2018-02-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O escalonamento de tarefas é um problema de otimização combinatória no qual tenta-se sequenciar da melhor maneira os trabalhos a serem realizados em processos de produção. O intuito neste caso é atingir os objetivos de desempenho estipulados pelo tomador de decisão, tais como, minimizar o makespan e minimizar o atraso total. O Problema de Sequencia-mento do tipo Job-Shop Flexível (FJSP) pertence a essa categoria, e caracteriza-se pela possibilidade de haver rotas tecnológicas diferentes para as tarefas e cada estágio poder ser composto por mais de uma máquina. Esse é o núcleo da tecnologia do gerenciamento de produção, pois sequenciamentos melhores podem encurtar o tempo de manufatura, reduzir os níveis de estoque, possibilitar a entrega de encomendas no tempo correto e aumentar a credibilidade dos processos e da empresa. Métodos exatos, que são computacionalmente custosos, são geralmente aplicados nos problemas de sequenciamento menores, portanto quando os problemas aumentam em tamanho, os métodos heurísticos e metaheurísticos começaram a ser aplicados. As metaheurísticas são importantes para solucionar FJSPs porque são mais rápidas do que os métodos exatos. Dentre elas, os Algoritmos Genéti-cos (AGs) estão entre as técnicas mais utilizadas para solucionar FJSPs e, atualmente, modelos híbridos vem sendo explorados, combinando AGs com técnicas de busca local e heurísticas para inicializar a população. No entanto, a escolha adequada dos parâmetros dos AGs é um trabalho difícil, recaindo num outro problema de otimização. Os Algoritmos Genéticos Adaptativos (AGAs) foram introduzidos para lidar com essa adversidade, uma vez que podem ajustar os parâmetros dos AGs durante o processo de busca. Portanto, o objetivo da presente dissertação é analisar diferentes técnicas adaptativas desenvolvidas para AGAs, com o intuito de reduzir o tempo de configuração dos AGs quando aplicados a FJSPs. Além disso, serão propostas alterações para as técnicas de atribuição de crédito e de seleção de operadores. Os estudos foram realizados em instâncias de diferentes tamanhos e os AGAs são comparados com AGs tradicionais. Duas diferentes análises foram realizadas baseadas em cenários no qual o tomador de decisão tem pouco tempo para configurar os algoritmos. Na Análise I, os AGAs tiveram desempenho semelhante aos AGs tradicionais, mas são interessantes por possuírem um menor número de parâmetros e, consequentemente, um menor tempo de configuração. Na Análise II, os AGAs geraram melhores resultados do que aqueles obtidos pelos AGs, o que os tornam apropriados para o caso em que há incerteza no processo produtivo e menor tempo de configuração. / Scheduling is a combinatorial optimization problem, in which one tries ordering the tasks to be performed in the processing units. The objective is to achieve the best values with respect to the performance indicators chosen by the decision-maker, such as, minimize the makespan and minimize the total lateness. The Flexible Job-Shop Scheduling Problem (FJSP) belongs to this category, and its characteristics are the different technological routes for the tasks and that each stage may consist of more than one machine. This is the technological core of the production management, as better schedules may reduce the manufacturing time, reduce the inventory, deliver the order in the right time, and raise the reliability of the process and the company. Exact methods, as they are computationally expensive, are usually employed for small scheduling problems, then heuristic and metaheuristic methods become interesting techniques for this type of problem. Metaheuristics are important to solve FJSPs as they are faster than the exact methods, and among then, Genetic Algorithms (GAs) are one of the most used techniques to solve FJSPs and, currently, they have been hybridized with local search and heuristics to initialize their population. However, to set up GAs is a hard-work and often generates another optimization problem. Adaptive Genetic Algorithms (AGAs) were introduced to work around this problem as they adapt the parameters of the GAs during the search process. Therefore, the objective of this dissertation is to analyze different adaptive techniques developed for AGAs with the purpose of reducing the setup time of GAs when they are applied to FJSPs. In addition, modifications will be proposed for the operator selection techniques and for credit assignment schemes. The studies were performed in instances of different sizes, and the AGAs are compared with traditional GAs. Two different analyzes were performed based on scenarios in which the decision maker does not has to much time to configure the algorithms. In Analysis I, some AGAs performed similarly to the traditional GAs, but they are more interesting as they have a smaller number of parameters, thus a shorter configuration time. In Analysis II, some AGAsgeneratedbetterresultsthanthoseobtainedbyGAs, whichmakesthemappropriate for the case when there is uncertainty in the production process and the decision maker does not have too much time to configure the algorithm.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2016-06-01T14:43:08Z No. of bitstreams: 1 Valdemar Modolo Junior.pdf: 2802590 bytes, checksum: f3956818acd10efc3244abc007294827 (MD5) / Made available in DSpace on 2016-06-01T14:43:08Z (GMT). No. of bitstreams: 1 Valdemar Modolo Junior.pdf: 2802590 bytes, checksum: f3956818acd10efc3244abc007294827 (MD5) Previous issue date: 2015-06-10 / Among the optimization methods, the Genetic Algorithm (GA) has been producing good results in problems with high order of complexity, such as, for example, the production scheduling problem in job shop environment. The production sequencing problems must be translated into a mathematical representation, so that the AG can act. In this process we came up a problematic, the choice between different ways to represent the solution as some representations have limitations, how to present not feasible and / or redundant solutions. Therefore the aim of this study is to conduct a comparative study between different representations of the solution in the AG in production sequencing problems in job shop environments. Two representations of the solution were analyzed, the priority lists based and based on order of operations and compared with a binary representation, in the context of sequencing problem set defined by Lawrence (1984). The results were evaluated according to the total processing time (makespan), the computational cost and the proportion of generated feasible solutions. It was noticed that the representation of the solution based on order of operations, which produced 100% of feasible solutions, was the one that showed the best results although no convergence to the best known solution to every problem. / Dentre os métodos de otimização, o Algoritmo Genético (AG) vem produzindo bons resultados em problemas com ordem de complexidade elevada, como é o caso, por exemplo, do problema de sequenciamento da produção em ambiente job shop. Os problemas de sequenciamento da produção devem ser traduzidos para uma representação matemática, para que o AG possa atuar. Neste processo surgi uma problemática, a escolha entre as diferentes formas de se representar a solução visto que algumas representações apresentam limitações, como apresentar soluções não factíveis e/ou redundantes. Portanto o objetivo deste trabalho é realizar um estudo comparativo entre diferentes representações da solução no AG em problemas de sequenciamento da produção em ambientes job shop. Duas representações da solução foram analisadas, a baseada em listas de prioridades e a baseada em ordem de operações e comparada com uma representação binária, no contexto do conjunto de problemas de sequenciamento definidos por Lawrence (1984). Os resultados foram avaliados em função do tempo total de processamento (makespan), do custo computacional e da proporção de soluções factíveis geradas. Percebeu-se que, a representação da solução baseada em ordem de operações, a qual produziu 100% de soluções factíveis, foi a que mostrou os melhores resultados apesar de não apresentar convergência para a melhor solução conhecida em todos os problemas.

Studien genomfördes på industriföretaget Gränges Finspång AB som är en producent av valsade aluminiumprodukter för värmeväxlare vilka används som komponenter främst inom bilindustrin och värme, ventilation och luftkonditionering. Aluminium är en miljöeffektiv råvara tack vare materialets naturliga egenskaper samt dess återanvändbarhet vilket har lett till att allt fler företag vill ta vara på dessa egenskaper vid tillverkning av klimatsmarta produkter. För Gränges Finspång AB har materialets aktualitet på marknaden inneburit en ökad efterfrågan på företagets produkter vilket i sin tur har satt ökad press på företagets produktionseffektivitet. Den produktionsprocess som studerades på företaget var en uppsättning maskiner – även kallade kallvalsverk – vilka kan liknas med en funktionell verkstad. Syftet med studien var att, med hjälp av optimeringsmetoder, ta fram en modell som kan användas som beslutsunderlag för sekvensering av produkter i företagets kallvalsverk. Utifrån intervjuer, granskning av interna dokument och en kvantitativ dataanalys genomfördes en kartläggning av Gränges Finspång AB:s hela produktionsflöde såväl som de processer unika för kallvalsprocessen. För sekvensering av företagets produkter tillämpades en linjär heltalsmodell vilken anger optimum för maximalt 14 produkter. Studien bekräftar att företagets kallvalsning är ett komplext produktionssystem ur ett schemaläggningsperspektiv. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

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.

This thesis aims to review and analyze the scheduling problem in general and Job Shop Scheduling Problem (JSSP) in particular and the solution techniques applied to these problems. The JSSP is the most general and popular hard combinational optimization problem in manufacturing systems. For the past sixty years, an enormous amount of research has been carried out to solve these problems. The literature review showed the inherent shortcomings of solutions to scheduling problems. This has directed researchers to develop hybrid approaches, as no single technique for scheduling has yet been successful in providing optimal solutions to these difficult problems, with much potential for improvements in the existing techniques. The hybrid approach complements and compensates for the limitations of each individual solution technique for better performance and improves results in solving both static and dynamic production scheduling environments. Over the past years, hybrid approaches have generally outperformed simple Genetic Algorithms (GAs). Therefore, two novel priority heuristic rules are developed: Index Based Heuristic and Hybrid Heuristic. These rules are applied to benchmark JSSP and compared with popular traditional rules. The results show that these new heuristic rules have outperformed the traditional heuristic rules over a wide range of benchmark JSSPs. Furthermore, a hybrid GA is developed as an alternate scheduling approach. The hybrid GA uses the novel heuristic rules in its key steps. The hybrid GA is applied to benchmark JSSPs. The hybrid GA is also tested on benchmark flow shop scheduling problems and industrial case studies. The hybrid GA successfully found solutions to JSSPs and is not problem dependent. The hybrid GA performance across the case studies has proved that the developed scheduling model can be applied to any real-world scheduling problem for achieving optimal or near-optimal solutions. This shows the effectiveness of the hybrid GA in real-world scheduling problems. In conclusion, all the research objectives are achieved. Finaly, the future work for the developed heuristic rules and the hybrid GA are discussed and recommendations are made on the basis of the results.

Le contexte de notre travail s'intéresse à l'ordonnancement d'un atelier de type job shop. L'objectif de la thèse concerne l'élaboration d'une méthode de résolution aussi bien dans le cas classique d'un ordonnancement relatif à la production que dans le cas beaucoup moins étudié touchant l'ordonnancement conjoint de la production et de la maintenance. Les algorithmes génétiques ayant fait leur preuve dans le domaine aussi bien mono objectif que multiobjectif seront à la base de notre étude. Etude faite tout d'abord sur un problème classique de job shop noté J / / Cmax , en ne tenant pas compte des contraintes de disponibilité des machines, puis en introduisant dans un deuxième temps l'aspect de maintenance préventive ayant des objectifs parfois antagonistes avec la production et qui nécessite une résolution multiobjectif. Notre contribution comporte deux volets. Le premier volet prend appui sur les solutions générées par un algorithme génétique qui sont étudiées par des méthodes d'apprentissage. Méthodes qui seront resituées dans le processus d'Extraction de Connaissance à partir des Données (ECD). Dans un soucis de validation et de comparaison par rapport aux travaux faits dans la communauté, la démarche proposée a été élaborée sur un problème classique de type J / / Cmax et sur des benchmarks connus. Le deuxième volet propose un algorithme génétique Pareto optimal résolvant le problème d'ordonnancement conjoint de la production et de la maintenance au sein du job shop. Cet algorithme génétique génère des solutions Pareto optimales. Solutions que nous validerons par des bornes inférieures. Nous optons pour la maintenance préventive systématique pour l'appliquer dans l'atelier de job shop. L'une des difficultés majeures de ce type de maintenance est le choix des périodes d'interventions. Nous proposons dans ce cadre deux méthodes de choix de périodes systématiques.

Tvarkaraščių sudarymo uždaviniai – viena iš sunkiau sprendžiamų problemų, kylančių įvairiose gamybinėse struktūrose, grupė. Darbo pradžioje supažindinama su bendrais tvarkaraščių sudarymo uždavinių bruožais ir jų sprendimo algoritmais. Detaliau nagrinėti šiame darbe parenkamas vienas sunkiausių gamybinių tvarkaraščių ir apskritai kombinatorinių optimizavimo uždavinių – darbo fabriko uždavinys (angl. job shop scheduling problem), kuris be abejo nėra tiksliai sprendžiamas per polinominį sprendimo laiką. Šio uždavinio pradiniai duomenys yra duotos darbų ir įrenginių aibės. Kiekvienas darbas apdorojamas specifine įrenginių tvarka. Uždavinio tikslas – minimizuoti visų darbų atlikimo laiką. Šiam uždaviniui spręsti pristatėme du apytikslius tabu – atkaitinimo modeliavimo bei paieškos kintamose aplinkose algoritmus, priklausančius metaeuristinių metodų šeimai. Iš tabu – atkaitinimo modeliavimo galima nesunkiai gauti paprastą tabu paiešką, tad prie dviejų minėtų algoritmų galima pridėti ir paprastąją tabu paiešką. Šiame darbe atlikta minėtų algoritmų programinė realizacija. Pristatytų algoritmų efektyvumui įvertinti ir algoritmų parametrų parinkimo rekomendacijoms pateikti, buvo pasirinkti gerai literatūroje žinomi bei sunkiau sprendžiami etaloniniai darbo fabriko uždavinių pavyzdžiai. Darbo pabaigoje pateikiamos minėtų algoritmų parametrų parinkimo rekomendacijos ir aptariamas algoritmų efektyvumas, kuris nagrinėtuose uždaviniuose nebuvo pastovus minėtų trijų algoritmų atvejais, t... [toliau žr. visą tekstą] / At the beginning of this work we introduce to the combinatorial optimization, scheduling problems and methods used to solve them. In computer science scheduling problems is considered strongly NP-complete. The combinatorial optimization problem considered in this paper is a static job shop problem scheduling arising in the manufacturing processes. In the static job shop scheduling problem, a finite number of jobs are to be processed by a finite number of machines. Each job consists of a prederminated sequence of task operations, each of which needs to be processed without preemption for a given period of time on a given machine. Tasks of the same job cannot be processed concurrently and each job must visit each machine exactly once. A schedule is an assignment of operation to time slots on a machine. The makespan is the maximum completion time of the jobs and the objective of the job shop scheduling problem is to find a schedule that minimizes the makespan. When the size of problem increases, the computational time of the exact methods grows exponentially. Therefore, the recent research on job shop and other scheduling problems is focused on heuristic algorithms. We also presented some meta-heuristic algorithms such as Tabu search – Simulated annealing (TS/SA), Tabu Search (TS), Variable Neighborhood Search (VNS) and showed their results on some job shop instances. At the end of this work we tell recommendations about choosing suitable parameters.

Problemas de sequenciamento são muito comuns, eles existem sempre que há uma escolha sobre a ordem em que várias tarefas podem ser realizadas. Seja o negócio uma companhia aérea, um hotel, um fabricante de computadores ou uma universidade, esses problemas fazem parte do cotidiano. A aplicação das técnicas de sequenciamento permite, por exemplo, a redução dos custos e o aumento na agilidade da cadeia de suprimentos, afetando as operações no inicio e no fim da cadeia de suprimentos pelo mundo inteiro. Este trabalho parte da intenção de abordar os princípios e as técnicas de Scheduling, com a finalidade de propor um modelo de sequenciamento para a solução de um problema em sistemas produtivos do tipo job shop com n tarefas e m máquinas, considerando os tempos de setup dependentes da sequência e tendo como horizonte de planejamento o curto prazo. O objetivo é o de minimizar a perda dos tempos não produtivos. Neste contexto, a pesquisa apresenta um enfoque tanto exploratório, quanto aplicado. Pode ser considerado exploratório, uma vez que a revisão da literatura é referência central para o desenvolvimento do modelo matemático. É aplicado considerando-se o desenvolvimento do modelo e avaliação de sua aplicabilidade. Sendo assim, a partir da definição do problema e desenvolvimento do modelo por meio do uso de técnicas matemáticas e abordagens da pesquisa operacional constatou-se que as conclusões tiradas podem inferir decisões para o problema real. Sendo que, as considerações aqui feitas têm por finalidade relatar os fatos constatados nos experimentos realizados, visando contribuir com futuras pesquisas na área. / Sequencing problems are very common, they happen every time there is a choice regarding the order in which several tasks can be performed. The business can be an airline, a hotel, a computer manufacturer or a university; these issues are part of their routine. The application of the sequencing techniques allows, for example, reducing the costs and fastening the supply chain all over the world. This work has an approach to Scheduling principles and techniques, with the objective of proposing a sequencing model for the solution of a problem in productive systems such as job shop with n tasks and m machines, considering setup times dependent on the sequence and adopting a short term planning. The goal is to minimize the waste of unproductive time. In this context, the research presents an approach both exploratory and applied. It can be considered exploratory, once that the literature review is a main reference to the development of a mathematical model. It is applied when we consider the development of the model and evaluation of its applicability. Thus, from the problem definition and the model development by the use of mathematical techniques and approaches of the operational research, we found that the conclusions drawn from the model might infer decisions for a real problem. The considerations shown here aim to report the facts given in the conducted experiments, intending to contribute to future researches in the area.

We develop an extension to the tactical planning model (TPM) for a job shop by the third author. The TPM is a discrete-time model in which all transitions occur at the start of each time period. The time period must be defined appropriately in order for the model to be meaningful. Each period must be short enough so that a job is unlikely to travel through more than one station in one period. At the same time, the time period needs to be long enough to justify the assumptions of continuous workflow and Markovian job movements. We build an extension to the TPM that overcomes this restriction of period sizing by permitting production control over shorter time intervals. We achieve this by deriving a continuous-time linear control rule for a single station. We then determine the first two moments of the production level and queue length for the workstation. / Singapore-MIT Alliance (SMA)