Author(s): Branquinho, Vasco Moreira da Fonseca
Date: 2013
Persistent ID: http://hdl.handle.net/10400.5/6586
Origin: Repositório da UTL
Subject(s): Escalonamento; makespan; problemas de escalonamento com sequências dependentes de tempos setup (JSP-SDST); NP-difícil; Branch-and-Bound; pesquisa em profundidade; Scheduling; job-shop scheduling problem with sequence dependent setup times (JSP-SDST); NP-hard; depth-first search
Mestrado em Decisão Económica e Empresarial
No processo produtivo de uma indústria de fitofarmacêuticos deparamo-nos com problemas no sequenciamento e afetação de tarefas necessárias a encomendas. Este estudo destina-se à fábrica da maior multinacional portuguesa no ramo dos agro-químicos. A SAPEC Agro aposta numa estratégia vencedora no negócio agrícola e, neste ramo, a competição não é entre empresas, mas sim entre as cadeias de abastecimento. Com o crescimento da empresa e a sua internacionalização, inserida num ambiente altamente competitivo, torna-se fundamental automatizar o processo de planeamento da produção, que até aos dias de hoje tem sido feito por um engenheiro industrial. O presente estudo tem como objetivo encontrar um sequenciamento de tarefas (scheduling), ou seja, determinar uma afetação ótima das tarefas às máquinas, minimizando o tempo de execução total (makespan). Este tipo de problema é um clássico da literatura e é conhecido como um problema de job-shop scheduling com uma sequência dependente de tempos de setup (JSP-SDST). Um JSP-SDST apresenta, uma complexidade NP-difícil. Sendo um problema de difícil otimização, constituiu, assim, um desfio nas áreas da Investigação Operacional e Ciência da Computação. A abordagem escolhida passou primeiramente por definir o espaço de soluções admissíveis (S.A.) e neste encontrar uma solução ótima (sob determinadas condições), através do algoritmo Branch-and-Bound, recorrendo-se particularmente ao tipo de pesquisa Depth First Search (B&B-DFS) no espaço das soluções admissíveis. Neste estudo são apresentados outros tipos de pesquisa, também baseados em B&B, por forma a avaliá-los. Foi desenvolvida uma interface gráfica centrada no utilizador para que este possa usufruir do presente estudo, sem ter de lidar com a complexidade envolvida. A interface gráfica implementada é viável e, em articulação com os procedimentos de otimização escolhidos, constitui uma mais-valia para a organização, esperando-se que possa vir a ser instrumento de trabalho futuro.
The production process in the plant protection industry, as in many other industries, faces very often problems on how to schedule tasks that need to be completed in order to respond to a given set of orders. This study is made for the largest Portuguese multinational company in the agro-chemicals business, SAPEC Agro. SAPEC Agro relies on a winning strategy on this business, a business where competition is made between supply chains instead of companies. To follow the company’s growth and its continuous internationalization process, inserted in a highly competitive environment, this project aims to maximize the automation and optimize the production planning, which is now made by an Industrial Engineer. This study’s main goal is to develop an algorithm that will be able to find the optimal solution (under certain constraints) for the scheduling of tasks in the production process. That means determining the best possible sequence of tasks to each machine in order to minimize the total makespan. This type of problem is classic in the literature, and it is known as a Job-Shop Scheduling Problem with Sequence Dependent Setup Times (JSP-SDST). The resolution of the JSP-SDST is difficult, as in terms of computational complexity it is considered an NP-Hard problem, thus being a challenge in the areas of Operations Research and Computer Science. As the problem is applied in an industrial environment, the scheduling is useful if the algorithms respond in a reasonable amount of time, allowing the production managers to get real-time support when decisions need to be taken. The chosen approach was first to define an admissible solution space (some constraints to the allocations were applied), and then to find the optimum through a Branch-and-Bound method which uses a Depth-First-Search as method of search in the solution space. Other search methods and heuristics, also based on Branch-and-Bound are applied as well, in order to meet the time complexity constraints. A graphical interface is developed allowing its use even by those unfamiliar with the complexity of the problem. Users need just to include the inputs (orders and quantities of each product) and the program generates a schedule for the input orders. This work’s main goal is the development of a program that would be useful and would add value to the organization in study, the SAPEC Agro.
