Desenvolvimento de um sistema de apoio à decisão para o planeamento da produção
Full text
DESENVOLVIMENTO DE UM SISTEMA DE APOIO À DECISÃO PARA O PLANEAMENTO DA PRODUÇÃO CÉSAR DUARTE DIAS DA SILVA DISSERTAÇÃO DE MESTRADO APRESENTADA À FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO EM ENGENHARIA INDUSTRIAL E GESTÃO M 2014
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção César Duarte Dias da Silva Dissertação de Mestrado Orientador na FEUP: Prof. Manuel Pina Marques Faculdade de Engenharia da Universidade do Porto Mestrado Integrado em Engenharia Industrial e Gestão 2014-07-15
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção ii
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção iii Aos meus Avós, Pais e Irmão
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção iv
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção v Resumo Embora as organizações possuam geralmente mecanismos automatizados destinados à calendarização das operações, verifica-se em alguns casos que aqueles não traduzem a realidade da produção. Os calendários gerados, para além de serem inadequados, chegam a ser inexequíveis, dado não verificarem as restrições tecnológicas que o processo impõe. Neste projeto, realizado em ambiente empresarial, foi estudado o problema de planeamento das operações produtivas de uma empresa industrial. O contexto produtivo em análise, um ambiente job shop, é um dos mais complexos e de difícil resolução. A calendarização manual das diversas operações produtivas, além de ser bastante difícil e demorada, não facilita a comparação entre calendários alternativos, a aplicação de diferentes critérios de prioridade e o cálculo de avaliadores de desempenho. Quando se opta por este tipo de abordagem, a elevada complexidade inerente aos processos produtivos força à utilização de regras simples e de reduzido esforço de cálculo numérico. No contexto produtivo analisado durante este projeto, o planeamento das operações é feito de forma essencialmente manual. Apesar de existir um sistema de informação com um módulo de planeamento, os calendários são gerados sem o seu suporte. Dadas as circunstâncias, e com o objetivo de flexibilizar e automatizar o processo de planeamento, foi desenvolvido um sistema de apoio à decisão capacitado para tempos de setup dependentes da sequência de operações. Apesar de ser definido um modelo de programação linear para o planeamento das operações, a obtenção de soluções ótimas para esse modelo exigiria a utilização de um software comercial de otimização específico de elevado custo. Por esse motivo foram implementados numa folha de cálculo modelos heurísticos baseados em regras de prioridade. A codificação desses modelos, e posterior integração numa interface assente em folhas de cálculo, levou à criação de um sistema de apoio à decisão. Este permite a geração de calendários de fabrico exequíveis através de diversos critérios de prioridade e a sua avaliação de desempenho. Verificou-se, após a realização de testes computacionais, que o sistema permite gerar os calendários pretendidos de forma intuitiva e em poucos segundos.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção vi
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção vii Development of a decision support system for the production planning Abstract Although organizations have often automated mechanisms for the operations scheduling sometimes, these systems doesn’t express the production reality. The schedules generated by these, besides being inappropriate, can be infeasible, due to breach of technological constraints that the process requires. In this project, realized in a business environment, the productive operations scheduling problem of an industrial company was studied. The productive context analysed, a job shop environment, it’s one of the most complex and difficult to solve. The operations scheduling handmade, in addition to being very difficult and time consuming, doesn’t facilitate the comparison of alternative schedules, the application of different priority criterions and the calculation of performance evaluators. When this approach is used, the high complexity inherent to production processes forces the use of simple rules and not involving a huge numeric calculation effort. In the productive context analysed during this project, the operations scheduling is essentially handmade. Despite existence of an information system with a production planning module, the schedules are generated without this support. Given the circumstances, and in order to increase the flexibility and automate the planning process, a decision support system able to consider sequence-dependent setup times was developed. Although has been defined a linear programming model for the operations scheduling, finding optimal solutions would require the use of optimization software with high cost. For this reason, heuristic models based on priority rules were implemented in a spreadsheet. The encoding of heuristic model, and subsequent integration of a spreadsheet-based interface, led to the development of the desired decision support system. This allows the generation of feasible production schedules through various priority criteria and their performance evaluation. It was found, after performing computational tests, that this system allows the achievement of desired production schedules intuitively and in few seconds.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção xiv
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção xv Índice de figuras Figura 1 – Missão, visão e compromissos da empresa .......................................................................... 2 Figura 2 – Etapas do processo produtivo da empresa ........................................................................... 3 Figura 3 – Representação da operação de maquinação de peças ........................................................ 4 Figura 4 – Representação do carácter cíclico da etapa de maquinação ................................................ 4 Figura 5 – Oportunidades de melhoria no processo de planeamento da produção ............................... 6 Figura 6 – Grafo disjuntivo para um problema ................................................................. 10 Figura 7 – Grafo disjuntivo acíclico para um problema .................................................... 11 Figura 8 – Diagrama de Gantt para um problema ........................................................... 11 Figura 9 – Classes de complexidade .................................................................................................... 12 Figura 10 – Modelos de solução ótima ................................................................................................. 13 Figura 11 – Modelos de aproximação ................................................................................................... 14 Figura 12 – Modelos de aproximação por pesquisa local ..................................................................... 15 Figura 13 – Abordagens de resolução: qualidade da solução versus tempo de execução.................. 18 Figura 14 – Níveis de planeamento ...................................................................................................... 19 Figura 15 – Página frontal de uma ordem de fabrico ............................................................................ 20 Figura 16 – Sequência de operações de uma ordem de fabrico .......................................................... 21 Figura 17 – Tempo de processamento das operações no atual modo de planeamento...................... 22 Figura 18 – Tempo de processamento das operações a considerar nos modelos .............................. 22 Figura 19 – Vista geral do ERP da empresa ......................................................................................... 23 Figura 20 – Recorte de uma folha de cálculo de planeamento da empresa ........................................ 24 Figura 21 – Recorte de uma folha de cálculo evidenciando a alocação de operações ........................ 24 Figura 22 – Diagramas de Gantt gerados pelo planeamento da produção. ......................................... 25 Figura 23 – Recorte de uma folha de cálculo de tratamento de indicadores ....................................... 26 Figura 24 – Representação do atraso de uma dada ordem de fabrico .............................................. 30 Figura 25 – Sobreposição de setups com operações para uma dada ordem de fabrico ................. 31 Figura 26 – Matriz de setup de uma dada máquina .......................................................................... 32 Figura 27 – Consecutividade de eventos de planeamento. .................................................................. 33 Figura 28 – Flowchart do algoritmo de sequenciamento de operações. .............................................. 37 Figura 29 – Flowchart da rotina auxiliar de definição das variáveis auxiliares e .............. 38 Figura 30 – Flowchart do algoritmo de calendarização de operações ................................................. 42 Figura 31 – Flowchart da rotina auxiliar de redefinição das variáveis auxiliares e ........... 43 Figura 32 – Sistema desenvolvido: definição inicial de um problema .................................................. 45
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção xvi Figura 33 – Sistema desenvolvido: parâmetros das máquinas e ordens de fabrico............................. 46 Figura 34 – Sistema desenvolvido: parâmetros das operações ........................................................... 46 Figura 35 – Sistema desenvolvido: matrizes de setup .......................................................................... 47 Figura 36 – Sistema desenvolvido: regras de prioridade. ..................................................................... 47 Figura 37 – Sistema desenvolvido: calendários gerados ...................................................................... 48 Figura 38 – Sistema desenvolvido: avaliadores de desempenho ......................................................... 49
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção xvii Índice de tabelas Tabela 1 – Avaliadores de desempenho do JSSP .................................................................................. 9 Tabela 2 – Índices dos modelos ............................................................................................................ 27 Tabela 3 – Avaliadores de desempenho na perspetiva da ocupação das máquinas ........................... 44 Tabela 4 – Dados gerais dos problemas analisados ............................................................................ 50
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção xviii
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 1 1 Introdução Os sistemas de software e os algoritmos de otimização para planeamento da produção começam a ganhar terreno face aos tradicionais sistemas manuais, em parte devido à contribuição de Henry Gantt. A descoberta protagonizada por Gantt, que permite a identificação de caminhos úteis para compreender as complexas relações entre Homens, máquinas, encomendas e o tempo, aliada à força das tecnologias de informação para recolher, visualizar, processar e partilhar os dados de forma rápida e fácil, permitiu agilizar e criar novas rotinas em processos de tomada de decisão (Herrmann 2006). Apesar de produzirem e enviarem bens para os seus clientes e mercados, muitas empresas não tiraram partido destes progressos. Nestas, o sistema de planeamento da produção não passa de uma coleção de planos independentes e não relacionados frequentemente ignorados e com informação pouco confiável (Herrmann 2006). Não raras vezes, as soluções informáticas implementadas estão inoperacionais, quer por quantidade excessiva de informação, quer por desconhecimento dos agentes de planeamento das funções incorporadas, ou até mesmo pela inaplicabilidade dos modelos à realidade produtiva das empresas (Marques 1993). Com a proliferação das novas tecnologias o acesso à informação torna-se mais fácil e célere. As empresas têm assim de procurar novas soluções, dotadas de qualidade e adequabilidade, por forma a responder aos requisitos de mercados informados e com distintas exigências. É necessário adotar mecanismos e rotinas ágeis e eficientes, tirando o máximo proveito dos recursos disponíveis. Um processo de tomada de decisão em sistemas de produção deverá considerar quatro classes de variáveis: custo, tempo, qualidade e flexibilidade. Os objetivos a atingir consistem em valores alvo, ou intervalos de valores, para uma dada variável (Chryssolouris 2006). O modelo tetraédrico desenvolvido por Chryssolouris (2006) enfatiza o inter-relacionamento entre as distintas classes de variáveis, advogando que não é possível otimizar simultaneamente o custo, o tempo, a qualidade e a flexibilidade. De acordo com Chryssolouris (2006) as variáveis relacionadas com o custo e o tempo são as mais utilizadas para avaliar quantitativamente o desempenho das empresas. Segundo Pinedo (2008) um dos métodos de tomada de decisão com maior importância em diversos ambientes produtivos e de processamento de informação é a calendarização das operações (scheduling). Jacobs e Chase (2011), argumentando que fluxo de trabalho equivale a fluxo de caixa, classificam-no como um elemento central do processo produtivo. Scheduling pode então ser definido como um processo de tomada de decisão que é usado regularmente em muitas indústrias de produtos e serviços. Ele lida com a alocação de recursos a tarefas sobre um dado período de tempo e o seu objetivo é otimizar um ou mais objetivos (Pinedo 2008, 1). O grande objetivo deste projeto visa a resolução de um problema de scheduling. Devidamente inserido num contexto técnico-científico, este projeto visa a análise e melhoria do processo de planeamento da produção de uma empresa industrial. Pretende-se a criação de um sistema de apoio à decisão convenientemente estruturado para o contexto empresarial a que se destina, um ambiente job shop, e que não deixe de lado, nem o poder das novas tecnologias, nem as considerações de Gantt relativas aos métodos de planeamento. Neste capítulo introdutório é apresentada a envolvente industrial que serviu de base à realização do projeto. Inicialmente faz-se uma breve apresentação da empresa onde decorreu o projeto, a KTK (Kristaltek – Laser e Mecânica de Precisão, Lda.), seguindo-se uma
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 2 descrição do seu processo produtivo e lógica de criação de valor. Na parte final desta secção, além de ser feito um posicionamento do projeto face à atividade da empresa, no qual se estabelece um vínculo entre os objetivos do projeto e o problema em análise, são apresentados os temas abordados ao longo do presente relatório. 1.1 Apresentação da KTK Foi no seio do setor têxtil que a KTK teve a sua origem. Inicialmente criada com a intenção de prestar apoio às máquinas e equipamentos de empresas do setor têxtil situadas no concelho de Barcelos, mais concretamente à parte mecânica e de manutenção, esta empresa foi aparecendo no mercado da mecânica de precisão oferecendo variadas soluções que, direta ou indiretamente, iam chegando a diversos clientes da indústria aeronáutica. A empresa foi-se equipando com máquinas, recursos e tecnologia, formalizando no ano de 2009 aquilo que viria a ser o nascimento de uma empresa tecnológica neste setor de atividade. A missão, a visão e os compromissos estabelecidos pela KTK podem consultados na Figura 1. Figura 1 – Missão, visão e compromissos da empresa. Por forma a conseguir satisfazer os mais diversos e rigorosos requisitos e especificações dos clientes, a KTK está devidamente certificada com as normas ISO9001 e AS9100. Estas normas autenticam o sistema de gestão da qualidade da empresa, dando ênfase à orientação que é dada ao cliente, nesta exigente área de maquinação de precisão por torneamento e fresagem. A certificação 9100 remete diretamente para a indústria aeroespacial e de defesa. Sabendo da exigência e competitividade dos mercados em causa, a KTK foi-se equipando, ao longo dos últimos anos, com meios tecnológicos, sistemas e processos que vêm permitindo a disponibilização de um leque alargado de soluções inovadoras e dotadas de qualidade perante os clientes. Tais soluções passam pela mecânica de precisão por torneamento e fresagem, pelo corte por eletro-erosão e jato de água, pela retificação de superfícies e ainda pela gravação a laser. Os centros de maquinação e os tornos afiguram-se como elementos produtivos com maior volume de produção. Os clientes da empresa são, na sua grande maioria, empresas inseridas nas cadeias de abastecimento de diversas indústrias. Salientam-se as indústrias aeronáutica, automóvel, de medicina e de defesa e ainda a indústria em geral. A atividade desta empresa desenrola-se nas suas instalações, situadas em Barcelos, onde se desenvolvem a atividade operacional e os processos administrativos. •Fornecer o melhor produto e serviço em termos de qualidade, prazo de entrega, competitividade e satisfação do cliente segundo o lema "NO LIMITS FOR SOLUTIONS". Missão •Ser um fornecedor de refêrencia em Portugal, em serviços de mecânica de precisão. Visão •Refletir nos sucessos a capacidade dos colaboradores; •Fazer do sistema de gestão AS9100 uma ferramenta para o futuro; •Estabelecer a melhoria como uma meta diária; •Estabelecer com cada cliente uma relação de parceria. Compromissos
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 3 Receção Maquinação Acabamento Inspeção Embalagem Expedição 1.2 Processo produtivo da KTK O processo de criação de valor na KTK, no qual se identificam cinco grandes etapas, tem o cliente como principal impulsionador. Este desencadeia o fluxo produtivo e é o destinatário dos produtos e serviços desenvolvidos, assumindo assim um papel central neste processo. Na Figura 2 estão representadas as etapas genéricas do processo produtivo. Figura 2 – Etapas do processo produtivo da empresa. Tudo começa com a identificação e análise de uma necessidade do cliente, que irá ser avaliada pelos responsáveis da área comercial. Após uma fase de negociação e orçamentação entre a empresa e o cliente, em caso de mútuo acordo, dá-se início o processo. Caso se trate do desenvolvimento de um produto novo é necessário proceder à sua industrialização. Aqui procede-se à criação dos modelos e dos desenhos técnicos (2D e 3D) que são peça essencial no desenrolar do processo produtivo. São também definidas quais as operações que darão origem ao produto final pretendido, bem como a sua sequência e alocação aos diversos equipamentos. Nesta etapa são ainda programadas as operações de maquinação, podendo haver recurso à criação e análise de simulações de produção. A estruturação das fichas de instrução, que farão parte da documentação que complementa a ordem de fabrico, bem como a verificação das necessidades de equipamento auxiliar são também realizadas nesta fase. Caso não se trate de um produto novo, procede-se ao lançamento da ordem de fabrico correspondente sem se passar pela industrialização do produto. A ordem de fabrico é um documento que serve de roteiro para o material em causa, dando orientações aos operários encarregues da prossecução das diversas operações. Nela constam as diversas etapas que compõem o processo, bem como as secções onde ocorrem e a respetiva sequência. Este documento contém ainda a referência do material em causa, a datas de lançamento e entrega e os tempos de setup e de processamento das diversas operações (ver secção 3.1). Após o lançamento da ordem de fabrico, procede-se à requisição de matéria-prima. Esta pode ter origem no próprio cliente, ou então, ser da responsabilidade da KTK. Caso se verifique esta última situação procede-se à averiguação das existências em inventário, e em caso de ser necessário adquirir, procede-se à encomenda perante fornecedores. Seguidamente dá-se a primeira etapa do processo produtivo, a receção da matéria-prima. Após ter dado entrada na empresa, o material é etiquetado com as devidas referências, para garantir um maior controlo sobre os stocks. É também efetuada uma verificação visual e dimensional ao material rececionado, principalmente no caso de este ser da responsabilidade da KTK. Neste caso, é também requerido ao fornecedor um certificado do material, por forma a isentar a KTK de qualquer responsabilidade no caso de alguma não conformidade relacionada com as suas propriedades. Nesta etapa procede-se ainda ao armazenamento do material, que posteriormente vai ser preparado (cortado, se necessário) para poder abastecer os vários postos de trabalho. A etapa seguinte é a da maquinação. Nesta fase são realizadas as diversas operações de maquinação que constam nas respetivas ordens de fabrico. Cada operação deste tipo consiste
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 4 na maquinação de uma série de peças, podendo ser necessário acrescentar previamente uma operação de validação da primeira peça (Figura 3). (a) (b) Figura 3 – Representação da operação de maquinação de peças. Grande parte das operações de maquinação de peças necessita de um mecanismo de validação da primeira peça (Figura 3 (a)). Este consiste, habitualmente, na maquinação de uma peça, a primeira na respetiva operação, que é inspecionada pelos técnicos de qualidade por forma a averiguar a sua conformidade. O objetivo é, contudo, analisar a conformidade do equipamento. Caso este esteja conforme, procede-se à maquinação das restantes peças (maquinação em série). Caso contrário, procede-se à correção do equipamento (acerto de cotas, afinação da máquina, por exemplo) até este estar conforme. Pode dar-se o caso da operação de maquinação não necessitar de uma operação prévia de validação da primeira peça. Esta situação é menos frequente que a anterior e, quando ocorre, a operação de maquinação apenas contempla a maquinação em série (Figura 3 (b)). Figura 4 – Representação do carácter cíclico da etapa de maquinação. Esta etapa do processo produtivo, a maquinação, é cíclica, pois este processo repete-se para todas as operações de maquinação que constam nas respetivas ordens de fabrico (Figura 4). Maquinação em série Validação da primeira peça Maquinação de peças Maquinação em série Validação da primeira peça Maquinação em série Maquinação de peças
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 5 Em seguida, passa-se para a etapa do acabamento, que antecede a inspeção de peças, na qual as peças são limpas e polidas, conforme os requisitos e tipologias das mesmas. Este é um processo essencialmente manual que se aplica a todas as peças das diversas séries. Daí resulta a relativa morosidade desta etapa. Segue-se a fase da inspeção, em que as diversas séries de peças são inspecionadas no laboratório de qualidade. É feita uma inspeção visual a todas as peças, sendo as inspeções dimensionais e geométricas feitas segundo critérios que advêm, quer dos padrões internos, quer das exigências dos clientes. Os resultados são devidamente registados nas folhas de inspeção que acompanham a ordem de fabrico. Caso seja necessário subcontratar alguma operação, as peças são expedidas para o respetivo agente, após esta etapa. As operações subcontratadas são, na maioria dos casos, operações para dar tratamento (de superfície, térmico, por exemplo) às peças. Após isto, as peças são então recebidas, voltando a ser inspecionadas pelos técnicos de qualidade. No caso de existirem peças não conformes, quer haja ou não subcontratação, as mesmas são, caso possível, retrabalhadas. Caso não seja possível, pode ser apresentado ao cliente um pedido de derrogação. Não sendo este aceite, ter-se-á que lançar em produção novas peças, caso o cliente ainda o pretenda. Caso contrário, a quantidade a enviar será inferior ao acordado. Finalmente vem a etapa do embalamento e expedição. As peças são embaladas conforme os requisitos e posteriormente expedidas para os clientes. Caso não sejam devolvidas por supostas não conformidades, tem assim fim o processo de criação de valor. Peças eventualmente excedentes são embaladas e posteriormente colocadas em armazém. Estão assim prontas para ser expedidas, quando necessário. 1.3 Posicionamento do projeto na atividade da KTK Na KTK, empresa que opera essencialmente numa lógica engineer-to-order 1 , e que se dedica ao fabrico de pequenas séries, o balanceamento dos recursos com a carga de trabalho assume particular importância. Para se conseguir satisfazer as necessidades dos clientes, sobretudo os prazos de entrega, é necessário fazer uma gestão racional dos recursos, garantindo uma elevada taxa de ocupação destes com tarefas de valor acrescentado. Fruto das sucessivas montagens e acertos dos equipamentos, devido às constantes trocas de ferramentas e demais acessórios, os tempos improdutivos, caracterizados por não acrescentarem valor diretamente, são um elemento importante na atividade operacional da empresa. A função planeamento da produção na KTK assume um papel importante na gestão dos tempos produtivos e improdutivos. É através desta atividade, tida como sendo de suporte, que é feita a alocação das diversas operações produtivas às máquinas disponíveis. Para se fazer uma análise aos tempos improdutivos, ao nível de se estudar com detalhe a sua origem e impacto, é importante perceber, desde logo, o modo como as operações são agendadas. Dada a complexidade do processo produtivo da KTK, do tipo job shop, o processo de calendarização das operações não é tarefa de fácil resolução. Apesar da teórica importância que esta tarefa assume, não existe um mecanismo automatizado que crie os diversos calendários de produção. Além do processo ser essencialmente manual, é notória a 1 Processo produtivo no qual a empresa trabalha com o cliente na conceção/design do produto, produzindo-o após a compra das matérias, partes e componentes necessários ao seu fabrico (Jacobs e Chase 2011).
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 12 Este tipo de diagrama é muito útil em ambiente de job shop. As restrições tecnológicas impedem a sobreposição de barras na mesma máquina e de barras correspondentes à mesma ordem de fabrico. Além de representar o tempo gasto para completar determinada operação, este diagrama permite averiguar o tempo improdutivo despendido em espera e setups pelas diversas ordens de fabrico e máquinas, de forma rápida e intuitiva. 2.5 Complexidade A noção de eficiência de um algoritmo, aquando da resolução de determinado problema, está normalmente ligada ao tempo necessário para alcançar uma solução final. Este tempo pode ser convenientemente expresso em termos de uma variável, o tamanho da instância do problema, que traduz a quantidade de dados necessária para descrever o problema (Garey e Johnson 1979). Um algoritmo de tempo polinomial, ou algoritmo “eficiente”, é aquele em que a função da complexidade é ( ( )) para qualquer função polinomial . O tempo necessário para alcançar a solução final é função polinomial da dimensão do problema. Já num algoritmo de tempo exponencial, ou algoritmo “ineficiente”, a função da complexidade é ( ( )) para qualquer função exponencial . Nestes, o tempo de execução do algoritmo é função exponencial de . Quando se está perante um problema de larga instância ( elevado), a distinção entre estes dois tipos de algoritmos assume particular importância (Garey e Johnson 1979; Papadimitriou 2003). A classe de problemas que podem ser resolvidos com algoritmos de tempo polinomial, ou de forma eficiente, é denominada por P. Já NP designa a classe de problemas cuja solução pode ser verificada em tempo polinomial, apesar de apenas poderem ser resolvidos com algoritmos de tempo polinomial não determinísticos. Um algoritmo não determinístico, contrariamente ao que acontece num algoritmo determinístico, pode revelar diferentes comportamentos em diferentes execuções. Um problema a resolver por um algoritmo deste tipo, tanto pode ser resolvido em tempo polinomial ou exponencial, consoante as escolhas tomadas ao longo da execução (Garey e Johnson 1979). Na ilustração seguinte apresenta-se um diagrama de Euler que evidencia as diferentes classes de complexidade. Figura 9 – Classes de complexidade (adaptado de Garey e Johnson (1979) e Papadimitriou (2003)). Os problemas mais difíceis da classe NP estão inseridos na classe NP-Complete. O tempo de resolução destes problemas cresce rapidamente com o aumento do tamanho da instância, fazendo com que estes problemas sejam frequentemente abordados com métodos heurísticos. Fruto da sua natureza combinatória, o tempo computacional de resolução destes problemas torna-se inviável, sujeitando assim a sua resolução a algoritmos de aproximação. Por último vem a classe de problemas NP-Hard. Os problemas inseridos nesta classe são pelo menos tão NP P NP-Complete Dificuldade NP-Hard - +
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 13 difíceis quanto os problemas NP-Complete mais difíceis, não sendo conhecidos algoritmos “eficientes” para a sua resolução. Também na resolução destes, são utilizados frequentemente métodos de aproximação para garantir soluções satisfatórias (Garey e Johnson 1979; Papadimitriou 2003). Os problemas do tipo job shop são amplamente reconhecidos como sendo dos de mais difícil resolução dentro da classe NP-Complete (Garey e Johnson 1979; Moghaddas e Houshmand 2008; Park e Lee 2012). O grau de complexidade destes problemas é mais elevado, caso se considerem os tempos de setups como sendo dependentes da sequência de operações (Sun e Noble 1999). Segundo Zandieh, Fatemi e Moattar (2006), os problemas de planeamento com este tipo de setups pertencem à classe de problemas de mais difícil resolução. Um JSSP deste tipo é classificado, segundo Park e Lee (2012), como NP-Hard. A natureza combinatória dos problemas de planeamento em job shop, aliada à imposição de restrições complexas, torna a sua otimização difícil e demorada. A utilização de heurísticas ou algoritmos de aproximação é assim justificada. 2.6 Abordagens de resolução Para problemas de dimensão real, é prática comum sacrificar-se a obtenção de uma solução ótima em detrimento de uma solução satisfatória, alcançada através de métodos heurísticos num curto espaço de tempo. Os modelos utilizados na resolução de JSSP podem assim ser divididos em duas classes: modelos de solução ótima e modelos de aproximação (Błażewicz, Domschke e Pesch 1996; Pacheco e Santoro 1999). 2.6.1 Modelos de solução ótima Como modelos de otimização destacam-se as técnicas de enumeração explícita e implícita. A programação inteira, o branch and bound e a programação dinâmica são abordagens usadas na resolução de JSSP numa lógica de enumeração implícita (Figura 10). Figura 10 – Modelos de solução ótima (adaptado de Pacheco e Santoro (1999)). Na enumeração total todas as soluções são avaliadas. A forma como são definidas as variáveis de decisão, as restrições e a função objetivo é que diferencia a forma como a solução é alcançada, pois não se utilizam características específicas para direcionar a procura da solução (Hillier e Lieberman 2001; Pacheco e Santoro 1999). Os problemas de JSSP podem ser formulados como problemas de programação linear e, em particular, de programação inteira. A formulação destes problemas contempla, além da função objetivo e de outras particularidades, dois grandes conjuntos de restrições: precedência de operações na mesma ordem de fabrico e limitação da capacidade das máquinas. Neste Modelos de solução ótima Explícita Enumeração total Implícita Programação inteira Branch and bound Programação dinâmica
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 14 método, o tempo de alcance de uma solução está condicionado às aplicações de software de otimização e do hardware disponíveis no momento. A técnica mais frequente na resolução de problemas de programação inteira ou inteira mista é o branch and bound. Esta técnica utiliza uma estrutura de procura em árvore para a construção da solução, analisando, a cada ramificação, os nós que estão qualificados. Um nó qualificado é aquele que apresenta um limite inferior da solução inferior ao limite superior (melhor solução completa já encontrada ou solução inicial). Os nós que não satisfaçam este requisito são descartados, eliminando-se todas as ramificações deles decorrentes. Os nós qualificados são desdobrados em novas soluções, de modo a ser possível encontrar soluções possíveis de melhor valor que o limite superior. Caso sejam encontradas, o limite superior é atualizado e a procura prossegue (Hillier e Lieberman 2001; Pacheco e Santoro 1999). As etapas genéricas deste método, segundo Hillier e Lieberman (2001), são as seguintes: i. Branching: divisão de um nó (problema) em dois ou mais nós (subproblemas); ii. Bounding: obtenção de um limite por nó que indica quão boa pode ser a solução; iii. Fathoming: seleção dos nós a ter em consideração na próxima etapa. A sua simplicidade, aliada à sua eficiência computacional, são as razões que, de acordo com Pinedo (2008), tornam o branch and bound bastante popular na resolução destes problemas. Na programação dinâmica, por oposição ao que acontece na enumeração explícita, muitas das soluções vão sendo eliminadas à medida que se vai enumerando. Esta técnica é utilizada para criar uma sequência de decisões inter-relacionadas. É feita uma divisão de cada problema em subproblemas, que vão sendo resolvidos sequencialmente até o problema inicial estar completamente resolvido. A decisão tomada em cada subproblema tem impacto nas decisões a serem tomadas em subproblemas subsequentes. Quando comparado com a enumeração explícita, este método permite grandes poupanças computacionais (Hillier e Lieberman 2001; Pacheco e Santoro 1999). 2.6.2 Modelos de aproximação As heurísticas de pesquisa local, as regras de prioridade 7 e a heurística shifting bottleneck são algoritmos de aproximação utilizados na resolução de JSSP (Błażewicz, Domschke e Pesch 1996). Os modelos assentes em heurísticas de pesquisa local, após explorar um subconjunto do espaço de soluções possíveis para os problemas, escolhem a solução que melhor desempenho apresenta. Os modelos baseados em regras de prioridade e na heurística shifting bottleneck denominam-se algoritmos de passo único (single-pass), visto construírem a solução de uma só vez, com apenas uma execução do algoritmo (Pacheco e Santoro 1999). Figura 11 – Modelos de aproximação. 7 Também designadas por priority rules ou dispatching rules. Algoritmos de aproximação Pesquisa local Regras de prioridade Heurística shifting bottleneck
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 15 As heurísticas de pesquisa local podem ser divididas em dois tipos relativamente à presença ou não de mecanismos de intensificação. Quando a pesquisa se dá de forma aleatória, sem a presença de mecanismos de intensificação, efetuam-se aleatoriamente trocas de posição entre as diversas ordens de fabrico, por forma a avaliar os resultados obtidos nas diversas soluções. Já na pesquisa com intensificação a procura ocorre de forma orientada à sequência de operações e/ou aos gargalos (Pacheco e Santoro 1999; Pinedo 2008). Quando a pesquisa com intensificação ocorre sem diversificação, apenas se altera a solução se isso corresponder a uma melhoria da função objetivo. Neste caso a pesquisa pode ficar restrita a uma região e a solução corresponder apenas a um ótimo local. Quando se verifica a presença de mecanismos de diversificação, o espaço de pesquisa é alargado para permitir que alternativas piores que a solução atual sejam também elas ponderadas, por forma sair das regiões que contêm ótimos locais. O tabu search, o simulated annealing e os algoritmos genéticos pertencem a esta categoria (Pacheco e Santoro 1999; Pinedo 2008). Figura 12 – Modelos de aproximação por pesquisa local (adaptado de Pacheco e Santoro (1999)). Tidos como algoritmos de melhoria, o simulated annealing e o tabu search permitem que, a partir de uma solução inicial, se gerem novas vizinhanças e novas soluções. Sempre que uma solução melhor que a anterior, ou que a inicial, é encontrada, o algoritmo tem-na como sendo a melhor. A principal diferença entre estes dois algoritmos está no critério de aceitação de novas soluções. No simulated annealing este critério é baseado num processo estocástico, enquanto que no tabu search é baseado num processo determinístico (Pinedo 2008, 382). O simulated annealing, técnica descrita por Kirkpatrick, Gelatt e Vecchi (1983), é baseado nos princípios da mecânica e da física, nos quais o processo de recozimento de uma substância engloba uma fase de aquecimento e, em seguida, uma fase de arrefecimento lento, para permitir a obtenção de uma estrutura cristalina. Com o decorrer do processo de otimização a solução atual vai sendo substituída por uma da sua vizinhança. A solução vizinha é selecionada com uma dada probabilidade, que depende da degradação da função objetivo (diferença na função objetivo entre a solução atual e a solução gerada pelo vizinho) e da temperatura atual (Talbi 2009). No tabu search, técnica proposta por Glover (1986), após a obtenção da solução inicial, é criada uma lista de movimentos de melhoria, dos quais se pretende a criação de uma solução melhor que a atual. Para cada um destes movimentos é criada uma nova vizinhança, sendo selecionado o melhor vizinho. Este mecanismo permite armazenar o historial de soluções numa lista tabu, impossibilitando que qualquer solução seja ponderada mais que uma vez (Pinedo 2008, 382). Modelos de pesquisa local Pesquisa aleatória Pesquisa com intensificação... ...sem diversificação ... com diversificação Tabu search Simulated annealing Algoritmos genéticos
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 16 Originalmente desenvolvidos por Holland (1975), os algoritmos genéticos são um método de pesquisa baseado em mecanismos de seleção natural. As suas técnicas de pesquisa permitem identificar a solução ótima, ou uma solução perto desta, nas populações de soluções criadas. Os algoritmos genéticos operam iterativamente (cada iteração corresponde a uma geração) num número fixo de soluções candidatas da população, designadas por cromossomas. Em cada geração os melhores cromossomas são levados a criar novas soluções (crianças) usando características de cada um dos pais. Os piores membros da população (com pior função objetivo) desaparecem para dar lugar a soluções mais aptas. Ao contrário do que acontece no simulated annealing e no tabu search, em que as vizinhanças são geradas a partir de uma única solução, nos algoritmos genéticos as vizinhanças são geradas combinando partes de diferentes soluções da população atual (Chaudhry 2012; Pinedo 2008) As regras de prioridade são provavelmente as heurísticas mais frequentemente usadas na resolução de JSSP na prática, devido à baixa complexidade computacional e à facilidade de implementação (Błażewicz, Domschke e Pesch 1996). Estas regras permitem a atribuição de prioridades às ordens de fabrico que estão em espera para processamento. Tais prioridades podem ser definidas a partir de atributos pertencentes às ordens de fabrico, operações, máquinas ou, ainda, ao estado da oficina. A dificuldade do processo de seleção da próxima operação a calendarizar resulta do facto de haver formas diferentes de sequenciar ordens de fabrico existentes numa dada fila de espera (Rajendran e Holthaus 1999). Quando o objetivo é a minimização da soma dos atrasos ou dos tempos de permanência das ordens de fabrico na oficina, a utilização destas regras é bastante frequente. Em ambientes extremamente imprevisíveis e complexos, tais como o do job shop, estas regras assumem grande utilidade (Baker 1998). A chegada intermitente de diversas ordens de fabrico aos centros de trabalho faz com que o número de calendários produtivos possíveis seja elevado. A simulação por computador é, neste caso, segundo Jacobs e Chase (2011), a única forma prática e viável de determinar o desempenho relativo das diversas regras de prioridade. Na literatura existe uma enorme diversidade de regras de prioridade. Blackstone Jr, Phillips e Hogg (1982) apresentam 34 regras, enquanto que Pinedo (2008) descreve 15 regras genéricas. Algumas dessas regras apresentam-se de seguida. São elas 8 : i. FIFO (First In First Out): é selecionada a operação que mais cedo chegou à fila de espera da respetiva máquina; ii. EDD (Earliest Due Date): é selecionada a operação correspondente à ordem de fabrico com menor data devida de entrega; iii. SPT (Shortest Processing Time): é selecionada a operação com menor tempo de processamento; iv. LWKR (Least Work Remaining): é selecionada a operação correspondente à ordem de fabrico com menor valor da soma das durações das operações ainda por processar; v. WINK (Work In Next Queue): é selecionada a operação correspondente à ordem de fabrico que tem a próxima operação a ser processada na máquina com menor carga; vi. MDD (Modified Due Date): é selecionada a operação com menor data de entrega modificada. A data de entrega modificada é obtida da seguinte forma: 8 , e representam respetivamente a data devida de entrega, o número de operações e o tempo de processamento da -ésima operação para uma dada ordem de fabrico . corresponde à operação presente na fila de espera a aguardar processamento e representa o instante de tempo atual.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 17 { ∑ ( ) } (1) vii. Min. Slack (Minimun Slack Time): é selecionada a operação correspondente à ordem de fabrico com menor folga. A folga é obtida da seguinte forma: ∑ ( ) (2) viii. Slack/OPN (Least Slack per Operation): é selecionada a operação correspondente à ordem de fabrico com menor folga por número de operações ainda por processar. ix. CR (Critical Ratio): é selecionada a operação com menor rácio crítico. O rácio crítico é obtido da seguinte forma: ∑( ) (3) x. RND (Random): é selecionada uma operação aleatoriamente. Caso as regras variem com o instante de tempo de sequenciamento, designam-se dinâmicas. Caso isso não aconteça, denominam-se estáticas (Pinedo 2008). A heurística shifting bottleneck, desenvolvida por Adams, Balas e Zawack (1988), é um método de aproximação que procura resolver o JSSP minimizando o makespan 9 total. As máquinas são sequenciadas uma a uma, iterativamente. A cada iteração, uma das máquinas ainda não sequenciadas é identificada como gargalo, sendo alvo de sequenciamento. O sequenciamento é feito como de um problema de máquina única se tratasse, com o auxílio da representação via grafos disjuntivos. Após uma máquina ser sequenciada, as sequências das restantes máquinas são reajustadas, tendo em conta as novas circunstâncias do problema (Adams, Balas e Zawack 1988; Pinedo 2008). 2.6.3 Análise crítica Na literatura é possível encontrar uma diversidade de estudos e considerações relativos à resolução de JSSP. Além das abordagens descritas anteriormente, existem muitas outras com particularidades e parâmetros específicos da situação ou estudo que lhes deu origem. A adequabilidade de tais modelos a situações práticas não é, contudo, uma garantia. Apesar de proporcionarem muitas e importantes considerações, os modelos da literatura não garantem, por si só, a resolução dos reais problemas da indústria. Estes devem ser estudados ao detalhe, por forma a ser possível determinar quais as verdadeiras restrições e variáveis em causa. Só após esta análise é possível definir com rigor o problema e modelar uma forma de o resolver. Os contributos da literatura fornecem, acima de tudo, linhas de orientação, que permitem fundamentar as estratégias de resolução a construir. Além disso, a envolvente tecnológica que rodeou esses trabalhos é bastante diferente da existente hoje em dia. Com a evolução da capacidade de cálculo dos computadores, dos softwares de otimização e hardwares disponíveis, é possível, nos dias de hoje, encontrar soluções ótimas num espaço de tempo reduzido, quando comparado com o de há uns anos atrás. No entanto, esses mecanismos têm custos elevados, difíceis de suportar pela maioria das empresas de pequena e média dimensão. Daí a importância dos métodos de aproximação que, fruto do seu baixo 9 Tempo necessário para o processamento de determinado conjunto de operações.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 18 custo exigência computacional, são muitas vezes utilizados, quer em contexto industrial, quer em contexto académico (Figura 13). Figura 13 – Abordagens de resolução: qualidade da solução versus tempo de execução. A análise às diferentes abordagens de resolução dos JSSP permite estabelecer uma relação entre a qualidade da solução e o tempo requerido para a obter. Apesar de não garantirem a solução ótima, os métodos de aproximação têm um tempo de execução razoável, podem ser utilizados em conjunto com outros métodos e mostram aderência a uma grande parte dos problemas reais. - + Tempo de execução Desvio à solução ótima - + Regras de prioridade Heurística shifting bottleneck Pesquisa local Modelos de solução ótima
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 19 3 Descrição do problema O planeamento da produção na KTK assenta na calendarização do processamento de um conjunto de ordens de fabrico. Apesar das ordens de fabrico utilizadas na empresa incluírem todas as operações a realizar numa dada série de peças (desde a receção até à expedição), o planeamento da produção foca-se na calendarização das operações de maquinação de peças. Esta função de planeamento é um processo de tomada de decisão de nível operacional, que se foca essencialmente no curto prazo (Figura 14). Figura 14 – Níveis de planeamento (adaptado de Guedes (2006)). Para efeitos de planeamento da produção, a KTK considera que as máquinas constituem o recurso mais escasso. A fase de maquinação é, por isso, a primeira a ser planeada. Faz-se em seguida, e em função do planeamento das operações de maquinação, o planeamento das etapas de acabamento, inspeção de qualidade e embalamento/expedição, que são essencialmente manuais. O planeamento destas etapas consiste, essencialmente, na alocação de recursos humanos e numa priorização das ordens de fabrico em circulação, em função do prazo de entrega. A própria alocação de operadores para as diversas máquinas, tal como o agendamento das diversas movimentações de material entre e para estas, é realizada após a calendarização das operações. Daí o pressuposto apresentado na secção 2.1, que refere que a capacidade das máquinas é o único recurso limitado. Isto justifica o facto da prioridade dada ao planeamento das operações de maquinação. A grande diferença entre o planeamento da produção da KTK e alguns dos JSSP abordados na literatura reside no facto de não haver qualquer relação entre o número de operações de maquinação por ordem de fabrico e o número de máquinas. Em diversos JSSP genéricos pressupõe-se que as ordens de fabrico visitam todas as máquinas uma vez. Tais pressupostos Horizonte de planeamento Meses Semanas Dias Planeamento estratégico Planeamento de vendas e marketing Planeamento da procura Planeamento de necessidades de materiais Planeamento da produção Planeamento do inventário Abastecimento de materiais Calendarização da produção Distribuição Produção Abastecimentos Entregas Clientes Fornecedores Estratégico Tático Operacional Anos
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 20 garantem que as diversas ordens de fabrico têm um número de operações constante e igual ao número de máquinas, o que não se verifica na KTK. Neste capítulo é apresentado com detalhe o problema abordado neste projeto. Numa primeira fase é analisada a estrutura das ordens de fabrico em circulação na KTK, bem como algumas considerações sobre os tempos de setup. É também exposto com pormenor o modo como os calendários da produção são gerados, bem como o modo como o seu desempenho é avaliado. 3.1 Ordens de fabrico As ordens de fabrico são um documento chave para o desenrolar do fluxo produtivo. Estas permitem aferir qual a sequência de operações que dará origem ao produto final pretendido, para uma dada série de peças. Nela constam várias informações acerca do cliente, do material utilizado e das diversas operações de maquinação. Na Figura 15 é possível visualizar a primeira página de uma ordem de fabrico, na qual é registado o controlo da entrada do material. Na página frontal desse documento, e para além da identificação da ordem de fabrico, é indicada a quantidade a produzir e da data devida de entrega na página frontal do referido documento. Figura 15 – Página frontal de uma ordem de fabrico. Identificação Prazo Quantidade
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 21 A cada operação que compõe o roteiro de fabrico, é atribuído um espaço na referida ordem de fabrico, no qual constam dados sobre a sua realização. A máquina onde a operação ocorre e a duração do seu processamento são exemplos de informações aí presentes (Figura 16). Há ainda campos em branco para serem preenchidos pelos colaboradores afetos à operação, onde é registada a quantidade de peças conformes e não conformes produzidas. Figura 16 – Sequência de operações de uma ordem de fabrico. Após o fim do fluxo produtivo (expedição ou armazenagem de produto acabado) a ordem de fabrico correspondente é fechada, sendo a informação constante nos campos preenchidos pelos colaboradores guardada para posterior tratamento e análise. As ordens de fabrico são assim um mecanismo de passagem de informação entre as diversas secções produtivas e não produtivas da empresa, acompanhando o material físico correspondente em todas as etapas da produção. 3.2 Tempos de setup No atual modo de planeamento da produção na KTK, o tempo de processamento das diversas operações de maquinação é composto de forma indistinta pelo tempo de setup, pelo tempo de validação da primeira peça e pelo tempo de maquinação em série (Figura 17). Apesar de nas ordens de fabrico os tempos de setup virem quantificados de forma isolada, para efeitos de planeamento estes são tratados como fazendo parte das diversas operações de maquinação, Máquina Duração
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 28 Relativamente ao atributo máquina, considere-se o seguinte parâmetro: data da disponibilidade inicial da máquina . Para finalizar resta referir os parâmetros gerais do modelo de planeamento: conjunto das ordens de fabrico; conjunto das máquinas; constante de valor muito elevado. São estes os parâmetros e as variáveis que servem de base à formulação do modelo matemático, isto é, que permitem definir as variáveis de decisão, as restrições e a função objetivo do problema. 4.2 Modelo matemático de programação linear 4.2.1 Variáveis de decisão As variáveis de decisão a seguir apresentadas, que apenas podem tomar valores não negativos, permitem aferir a hora de início das diversas operações, bem como a respetiva sequência das mesmas em cada uma das máquinas. São elas: O modelo proposto é então o seguinte: ∑( ) ∑( { }) (4) Sujeito a: [ ] ∑ ∑ ( ) [ ] (5) ∑ ∑ ( ) [ ] (6) (7) data de início do processamento da operação ; { { { se a operação for realizada após a operação , caso contrário; se a operação for a primeira a ser realizada na máquina , caso contrário; se a operação for a última a ser realizada na máquina , caso contrário.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 29 { } (8) { } (9) [ ] ( ) ∑ ∑ ( ) [ ] (10) [ ] (11) ( ) [ ( ) ∑ ∑ ( ) [ ] ] (12) [ ] (13) ∑ ∑ ( ) [ ] ∑ ∑ ( ) [ ] (14) ∑ ∑ ( ) [ ] (15) ∑ ∑ ( ) [ ] (16) [ ] [ ]: ( ) (17)
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 30 [ ] [ ] { } (18) 4.2.2 Função objetivo Para o modelo apresentado optou-se por uma função objetivo assente num critério baseado nas datas devidas de entrega das ordens de fabrico. O cumprimento dos prazos, sendo um fator importante para garantir a satisfação dos clientes, é um indicador chave para o controlo e monitorização da atividade operacional da empresa. A KTK, em termos genéricos, não associa diretamente qualquer benefício ou custo ao facto de terminar uma dada ordem de fabrico antes da data devida de entrega (a eventual criação de stock de produto acabado é uma decisão estratégica). As penalizações ou bonificações baseadas no término antecipado das ordens de fabrico relativamente à data devida de entrega (earliness e lateness) deixam assim de fazer sentido. Optou-se por isso pela minimização da soma dos atrasos (tardiness). Trata-se de um indicador baseado numa penalização a incorrer pelos atrasos na conclusão das várias ordens de fabrico relativamente às suas datas devidas de entrega (Figura 24). Figura 24 – Representação do atraso de uma dada ordem de fabrico (adaptado de Pinedo (2008)). Na resolução deste problema da empresa assume-se que a penalização a incorrer pelo atraso é proporcional à dimensão deste. Rajendran e Holthaus (1999) referem que é prática comum minimizar-se uma medida de desempenho baseada no atraso, em que a penalização a incorrer por este é diretamente proporcional ao período de tempo de atraso. Definiu-se assim como objetivo a minimizar a soma dos atrasos das ordens de fabrico (expressão (4)), visto ser um indicador que permite penalizar com magnitudes diferentes os atrasos de dimensão diferente e que engloba todas as ordens de fabrico. Em termos matemáticos, a minimização da soma dos atrasos equivale à minimização do atraso médio, pois o número de ordens de fabrico num dado evento de planeamento é constante. Apesar da importância dos atrasos, qualquer outro avaliador de desempenho dos calendários pode ser utilizado como função objetivo do modelo matemático. A fórmula de cálculo de diversos indicadores de desempenho, relativos às ordens de fabrico ou às máquinas, é descrita na secção 4.4.5. Com estas fórmulas, é assim possível reformular a função objetivo consoante os dados e objetivos do momento. Caso se queiram conjugar dois ou mais avaliadores como objetivos a minimizar, pode inclusive ser definida uma função objetivo multicritério. 4.2.3 Restrições As duas primeiras restrições apresentadas garantem a existência de apenas uma sequência de operações em cada máquina. A restrição (5) garante que cada operação, no caso de não ser a Penalização
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 31 primeira a realizar na máquina, apenas tem uma outra operação antecedente. Por seu lado, a restrição (6) garante que cada operação, no caso de não ser a última a realizar na máquina, apenas tem uma outra operação subsequente. A restrição (14) assegura que a primeira operação a realizar numa dada máquina apenas pode ter o seu início após a realização do setup inicial. Já este apenas pode ser realizado quando a máquina estiver disponível. As restantes operações, nessa mesma máquina, apenas podem ser realizadas após a hora de término da operação antecedente respetiva (non preemption), acrescida da duração do respetivo setup. Esta imposição, materializada através da restrição (17), garante a não sobreposição de operações e setups nas diversas máquinas. A restrição (10) permite assegurar, caso seja imposto, que o setup de determinada operação apenas se inicia quando a respetiva operação já está em espera na máquina onde vai ser realizada. Tal situação está representada na Figura 25 (a). Nesta situação, quando há duas operações consecutivas de uma dada ordem de fabrico, a realizar em máquinas diferentes, o setup de preparação da máquina para a segunda operação, apenas pode ter início após o término da operação anterior correspondente à ordem de fabrico, apesar de esta ser realizada noutra máquina. Caso isto não seja imposto, tal como representado na Figura 25 (b), há apenas que garantir a normal sequência e não sobreposição de operações dentro das ordens de fabrico, tal como a restrição (11) indica (overlapping não permitido). A restrição (12) garante que as ordens de fabrico apenas se iniciam após a data mínima de início. (a) – Situação em que . (b) – Situação em que . Figura 25 – Sobreposição de setups com operações para uma dada ordem de fabrico . É importante assegurar que operações consecutivas de uma dada ordem de fabrico a realizar na mesma máquina sejam processadas na respetiva máquina sem a inclusão de uma operação de uma qualquer outra ordem de fabrico entre estas. Esta restrição, formulada com a equação (13), garante a possibilidade de processamento simultâneo de mais do que uma operação da mesma ordem de fabrico, situação passível de ocorrer sob determinadas circunstâncias. Esta última situação não é estabelecida, no entanto, por questões de planeamento da produção. Dependendo da tipologia das peças, do operador da máquina, do código de maquinação e dos tempos de ciclo das operações, pode dar-se o caso de serem maquinadas duas operações consecutivas da mesma ordem de fabrico de uma só vez. A ocorrência desta situação não é
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 32 conhecida à data do evento de planeamento, não podendo por isso ser considerada com a máxima precisão. Sabe-se, contudo, que a restrição (13) tem ligação à realidade produtiva da KTK. Quando duas operações consecutivas da mesma ordem de fabrico são realizadas na mesma máquina, pretende-se que as mesmas sejam realizadas consecutivamente na respetiva máquina. Com isto podem-se, eventualmente, eliminar movimentações e armazenamentos temporários de material na oficina, bem como de toda a documentação associada. A própria matriz de setups construída para cada máquina terá que representar quais as sequências exequíveis de operações. Nas diversas matrizes apenas podem figurar valores para operações capazes de ocorrer uma após a outra. A ausência de qualquer valor reflete a impossibilidade de duas operações poderem ocorrer consecutivamente (Figura 26). Operação subsequente Operação precedente 1ª Figura 26 – Matriz de setup de uma dada máquina . De acordo com a representação anterior, sabe-se que a máquina tem seis operações a realizar, pertencentes a 3 ordens de fabrico distintas. Os campos sem valor representados a verde impõem a realização consecutiva, na respetiva máquina, de operações consecutivas referentes à mesma ordem de fabrico – restrição (13). Já os campos sem valor sinalizados a vermelho impõem a normal sequência dentro da mesma ordem de fabrico – restrição (11). Referir que a primeira linha da matriz representa a primeira operação a realizar na máquina . Garante-se também que cada máquina tenha uma e uma só operação inicial – restrição (15) – e operação final – restrição (16). Isto permite evitar a consideração de operações fictícias correspondentes à primeira e à última operação a realizar em cada máquina. Assegura-se também a atribuição de valores não negativos à variável – restrição (7) – e que as variáveis , e se comportam como variáveis binárias – restrições (8), (9) e (18) respetivamente. 4.3 Consecutividade de eventos de planeamento É necessário garantir que, aquando de um novo evento de planeamento, o planeamento feito até à data não seja totalmente desprezado. O modelo apresentado está precavido para tal
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 33 situação, bastando apenas quantificar certas variáveis na instância de dados. A Figura 27, que ilustra dois eventos de planeamento consecutivos, mostra como o preenchimento dos dados permite uma correta passagem de informação entre eventos de planeamento consecutivos. As operações já iniciadas aquando do novo evento de planeamento não devem ser interrompidas (non-preemption), tal como ilustradas para a máquina . A disponibilidade inicial dessa máquina no novo evento de planeamento deve contemplar o tempo necessário para a sua conclusão. As operações já planeadas no primeiro evento e que não foram fixadas para o evento atual (operações remanescentes) estão em pé de igualdade com as novas operações (novas ordens de fabrico) inseridas no sistema para um novo evento de planeamento. Neste caso, é necessário atualizar (redefinir) os índices das operações ( ) e das ordens de fabrico ( ) que permanecem em circulação. Figura 27 – Consecutividade de eventos de planeamento. Os tempos de setup considerando que as operações são as primeiras a realizar na máquina (primeira linha da matriz – Figura 26), são, na prática, tempos de setup entre duas operações, sendo a precedente conhecida. O modelo tratá-los-á como sendo setups iniciais, sendo os seus valores já inseridos na instância de dados tendo conhecimento da operação prévia (fora do evento de planeamento). Pode dar-se o caso de a disponibilidade inicial, , ser ditada, não por operações em curso, mas por indisponibilidade técnica (avaria), ações de manutenção, limpeza, entre outros. Nesse caso, o setup inicial estipulado terá que ter esse facto em consideração. Cabe ao agente de planeamento fazer um levantamento atento dos dados, e posterior inserção e tratamento dos mesmos no modelo, por forma a garantir um correto e eficaz evento de planeamento. 4.4 Modelo heurístico A determinação de uma solução ótima para o modelo matemático apresentado na secção 4.2 obrigaria à utilização de software comercial de otimização que a KTK não dispõe, e cujo custo é elevado. Por esse motivo optou-se por propor uma abordagem heurística baseada em regras de prioridade. Quando comparada com outras estratégias construtivas, a resolução através de regras de prioridade revela-se menos complexa e de maior aplicabilidade prática. Esta abordagem, apesar de teoricamente não permitir o alcance da solução ótima, garante a
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 34 criação de calendários produtivos num intervalo de tempo muito reduzido, o que por si só, já compensa um eventual desvio da solução face ao seu valor ótimo. Foram incorporadas 7 regras de prioridade no sistema de apoio à decisão desenvolvido. O algoritmo de sequenciamento de operações construído, que está apresentado na secção 4.4.2, permite sequenciar e calendarizar todas as operações de um conjunto de ordens de fabrico. Sempre que é necessário proceder à seleção de uma operação na fila de espera de uma determinada máquina, este algoritmo recorre ao método de seleção da próxima operação, que está apresentado em pormenor na secção 4.4.3. Para proceder à calendarização efetiva das operações, ou seja, à definição da sua hora de início de processamento, este algoritmo recorre ao algoritmo de calendarização de operações, que está descrito na secção 4.4.4. O algoritmo de sequenciamento de operações funciona como a principal rotina do modelo heurístico proposto, enquanto que o método de seleção da próxima operação e o algoritmo de calendarização de operações assumem o papel de sub-rotinas. Nesta secção expõe-se pormenorizadamente a heurística desenvolvida, através de uma descrição detalhada das suas variáveis e rotinas, bem como da sua inter-relação. No final, é ainda apresentada a fórmula de cálculo dos avaliadores de desempenho dos calendários. 4.4.1 Nomenclatura De seguida são definidos algumas variáveis e conjuntos de operações que, juntamente com os parâmetros apresentados na secção 4.1, permitem a definição do modelo heurístico. Relativamente às máquinas, considerem-se os seguintes conjuntos de operações e variáveis: conjunto de operações já sequenciadas na máquina ; conjunto de operações em fila de espera na máquina ; conjunto de operações a ser adicionadas à fila de espera da máquina ; data em que a máquina fica livre; última operação calendarizada na máquina até ao instante considerado; { Considerem-se as seguintes variáveis relativas às operações: data a partir da qual a operação está disponível para processamento; operação a calendarizar no instante considerado; data mínima de início do processamento da operação . Quanto aos setups, considerem-se as seguintes variáveis: As variáveis auxiliares e permitem identificar, em qualquer instante do processo de sequenciamento, quais as possibilidades de consecutividade entre operações, bem como a possibilidade de uma operação ser a primeira a processar respetiva máquina. Na fase inicial do processo de planeamento, estas variáveis devem estar em concordância com a matrizes de { { se a máquina ainda não tem nenhuma operação calendarizada, caso contrário. se o setup ainda pode ser realizado, caso contrário; se o setup ainda pode ser realizado, caso contrário.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 35 setup, pois as variáveis e têm correspondência com os parâmetros e respetivamente. Os campos sem valor da matriz de setup (representados na Figura 26 a verde, vermelho e cinzento) devem corresponder a variáveis e de valor 0. Já os campos com valor da matriz devem corresponder a variáveis e de valor 1. Considerem-se ainda as seguintes variáveis genéricas: data do instante de sequenciamento (data do relógio); data do instante de sequenciamento anterior; tempo acumulado entre operações consecutivas12 a realizar na mesma máquina; Com o desenrolar do algoritmo, as variáveis e vão sendo redefinidas à medida que as possibilidades de consecutividade entre operações se tornam inexequíveis. As variáveis em causa passam a assumir o valor 0 em vez do valor 1. No final do processo de planeamento apenas têm valor 1 as variáveis que representam respetiva e efetivamente a primeira operação a realizar na máquina e a consecutividade entre operações. Após o processo estar concluído, é possível fazer um paralelo entre as variáveis as variáveis de decisão do modelo matemático respetivamente, pois representam o mesmo. Nas secções 4.4.2 e 4.4.4, além dos algoritmos propostos serem descritos passo a passo, são também apresentados em forma de flowchart. Os processos de definição inicial e redefinição das variáveis e pertencentes ao algoritmo de sequenciamento de operações e ao algoritmo de calendarização de operações respetivamente, são tratados como rotinas auxiliares e, por questões de simplificação, apenas são exibidos pela via gráfica. Na secção 4.4.3 detalha-se o método de seleção da próxima operação. 12 Operações consecutivas na respetiva ordem de fabrico. { se existem operações consecutivas12 a realizar na máquina, caso contrário.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 36 4.4.2 Algoritmo de sequenciamento de operações i. Inicializar: (a) definir os conjuntos e : (19) (b) definir as variáveis e : (20) (21) (c) definir as variáveis e (ver Figura 29) (d) criar as operações iniciais das ordens de fabrico nas filas de espera: (22) { } (23) (e) definir a variável : { { } { }} (24) ii. Verificar as filas de espera: Se ⋃( ) seguir, caso contrário seguir para o passo iv. iii. Sequenciar as operações: (a) atualizar os conjuntos : (25) (b) iniciar o ciclo para as máquinas: (26) (c) se seguir, caso contrário ir para o passo (f); (d) redefinir as variáveis e e atualizar o conjunto : (27) { } (28) (29) (e) retornar ao passo ii; (f) se seguir, caso contrário voltar ao passo (c) com ; (g) se ( ) seguir, caso contrário voltar ao passo (c) com ; (h) redefinir as variáveis : { } ( ) (30) (i) selecionar a próxima operação (secção 4.4.3); (j) aplicar o algoritmo de calendarização de operações (secção 4.4.4); (k) redefinir a variável auxiliar : (31) (l) se seguir, caso contrário voltar ao passo (c) com ; (m) criar a próxima operação da ordem de fabrico: (32) { } (33) (n) retornar ao passo (c) com . iv. Terminar.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 37 Figura 28 – Flowchart do algoritmo de sequenciamento de operações. Não { } { { } { }} Iniciar { } Terminar ? Selecionar a próxima operação (secção 4.4.3) { } Aplicar o algoritmo de calendarização de operações (secção 4.4.4) ( ) { } Sim Sim Não Não ⋃( ) Definir as variáveis e (ver Figura 29) Sim ( ) Sim Não
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 44 Tabela 3 – Avaliadores de desempenho na perspetiva da ocupação das máquinas. Notação Máquina Tempo em setups Tempo desocupado Tempo total improdutivo Para o seu cálculo é necessário considerar a seguinte variável: intervalo de planeamento da máquina Esta variável permite aferir a dimensão da janela de planeamento para uma dada máquina, através da seguinte forma: { } (74) A fórmula de cálculo dos avaliadores mencionados é a seguir apresentada. ∑ ∑ ( ∑ ∑ ( ) [ ] ) [ ] (75) ∑ ∑ ( ) [ ] (76) (77) Podem também ser calculados avaliadores percentuais nesta perspetiva, à semelhança do que acontece na perspetiva das ordens de fabrico. Basta apenas fazer um rácio entre qualquer uma das variáveis , e e a variável , para uma qualquer máquina , conforme a medida percentual pretendida. Estes avaliadores podem também ser obtidos utilizando-se os valores totais das referidas variáveis, caso se pretendam avaliadores globais e não relativos a apenas uma máquina. Caso se pretenda inserir avaliadores deste tipo na função objetivo do modelo matemático, as variáveis e devem ser respetivamente substituídas pelas variáveis e do respetivo modelo. Para todos os avaliadores referidos, à exceção dos percentuais, é possível a obtenção dos seus valores médio e máximo. O valor médio de um avaliador é obtido pela divisão do seu valor total pelo número de elementos. O valor total corresponde a soma do valor do avaliador de todos os elementos. Caso se trate de um avaliador relativo às ordens de fabrico, o número de elementos corresponde ao número de ordens de fabrico. Num avaliador relativo às máquinas, o número de elementos corresponde ao número de máquinas. ( )
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 45 5 Sistema de apoio à decisão desenvolvido Nesta secção é apresentado o sistema de apoio à decisão desenvolvido. Além de se apresentar o funcionamento e a interface do sistema, explica-se também como foram realizados alguns testes de avaliação de desempenho do sistema. Apesar de ser difícil comparar com detalhe a performance deste sistema com a do modo de planeamento atual da empresa, foram utilizados dados do histórico de ordens de fabrico da KTK. Esta abordagem permite testar o sistema na envolvente industrial que lhe deu origem e propósito, fazendo com que a análise de sensibilidade às diferentes regras de prioridade seja feita com dados mais realistas. 5.1 Interface e modo de funcionamento O modelo heurístico descrito na secção 4.4 foi codificado em linguagem Visual Basic através de uma interface em Office Excel. O fácil acesso a este software, aliado à sua versatilidade e aplicabilidade para efeitos de cálculo, levaram a que se optasse pelo seu uso. O sistema de apoio à decisão foi desenvolvido por forma a facilitar a sua utilização. A interface em Office Excel, além de permitir uma fácil inserção dos dados, garante a construção e exibição dos planos de fabrico em poucos segundos. Para definir um novo problema de planeamento, é necessário, em primeiro lugar, inserir no sistema o número de máquinas e ordens de fabrico a considerar. Para isso, na folha inicial do sistema, existe um botão que permite dar início ao processo (Figura 32). Figura 32 – Sistema desenvolvido: definição inicial de um problema. Após o botão “Iniciar” ser pressionado, o sistema abre uma janela para a inserção do número de máquinas a considerar no evento de planeamento. Em seguida este processo repete-se para a definição do número de ordens de fabrico a considerar. Na etapa seguinte é necessário proceder à definição dos parâmetros relacionados com as máquinas e com as ordens de fabrico. Relativamente às máquinas, apenas é necessário inserir no sistema a hora da disponibilidade inicial de cada uma delas. Quanto às ordens de fabrico, insere-se a hora de início de processamento mínima, a data devida de entrega, o número de operações e o valor da variável binária que reflete a possibilidade, ou impossibilidade, da sobreposição de setups com operações (Figura 33).
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 46 Figura 33 – Sistema desenvolvido: parâmetros das máquinas e ordens de fabrico. Segue-se a inserção dos dados relativos às operações. Existe uma lista para cada ordem de fabrico, na qual constam as suas operações. Nessas listas, é necessário inserir para cada operação a duração do processamento e a máquina onde ela é realizada (Figura 34). Figura 34 – Sistema desenvolvido: parâmetros das operações. O passo seguinte consiste na construção das matrizes de setup. Para cada máquina é automaticamente criada uma matriz de setup, onde apenas constam as respetivas operações. Para auxiliar o utilizador do sistema, e para evitar a ocorrência de erros, apenas é possível a inserção de tempos de setup em células correspondentes a possibilidades de consecutividade exequíveis. As restantes células das matrizes estão sinalizadas e bloqueadas à edição, o que facilita o seu preenchimento por parte do utilizador (Figura 35).
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 47 Figura 35 – Sistema desenvolvido: matrizes de setup. Após a inserção de todos os parâmetros no sistema, falta apenas necessário selecionar a regra de prioridade que será utilizada para determinar qual a próxima operação a ser calendarizada. Consoante os dados do evento, e o objetivo a atingir, as diferentes regras podem ter desempenhos diferentes. É assim necessário analisar qual a regra que melhor se adequa às circunstâncias do momento (Figura 36). Figura 36 – Sistema desenvolvido: regras de prioridade. O sistema desenvolvido permite que o utilizador faça uma rápida análise de sensibilidade às diferentes regras de prioridade consoante os dados do momento. É possível determinar quais as regras que apresentam melhor desempenho, mediante determinado critério de prioridade. Nas duas primeiras caixas de seleção apresentadas na Figura 36 estão listados os avaliadores de desempenho dos calendários gerados. Uma contém os avaliadores na perspetiva das ordens de fabrico, e a outra os avaliadores na perspetiva da ocupação das máquinas (descritos na
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 48 secção 4.4.5). Após se selecionar quais os indicadores a analisar, um de cada tipo, é apenas necessário clicar no botão “Obter”. O sistema imprime, junto à respetiva caixa de seleção, quais as regras que apresentam melhor desempenho consoante os indicadores selecionados. No exemplo presente na Figura 36, as regras MDD, EDD e Min. Slack são, entre as definidas no sistema, as que geram calendários nos quais o tempo de setup médio é menor. Já as regras ERD/FIFO, SSPT, Slack/OPN e CR são, entre o lote de regras de prioridade definidas, as que geram calendários nos quais a antecipação na conclusão média das ordens de fabrico é menor. Após fazer uma breve análise de sensibilidade as diferentes regras, o utilizador pode agora selecionar a regra de prioridade mais adequada às circunstâncias do momento. As 7 regras de prioridade definidas estão listadas na terceira caixa de seleção apresentada na Figura 36. Basta apenas selecionar a pretendida e clicar no botão “Calendarizar”, para que o calendário seja gerado e impresso na folha de cálculo seguinte (Figura 37). Figura 37 – Sistema desenvolvido: calendários gerados. Apesar do diagrama de Gantt ser a forma mais usual para representar calendários produtivos, optou-se por imprimir os calendários gerados pelo sistema de apoio à decisão sob a forma de listas. Através desta representação são criadas duas listas independentes, uma relativa às máquinas e outra relativa às ordens de fabrico, na qual constam a hora de início e término das respetivas operações. Na lista relativa às máquinas constam ainda os setups. No canto superior esquerdo da folha de cálculo são apresentados o tempo de execução do sistema e o número de decisões (seleção da próxima operação) que foi necessário tomar através de regras de prioridade. À frente deste valor, é possível ver-se, entre parêntesis, o número médio de operações presentes na fila de espera por decisão deste tipo. O tempo de execução exibido pelo sistema corresponde ao tempo (minutos) necessário para gerar a solução. Inclui ainda o tempo que o sistema gasta na leitura e armazenamento dos dados e na impressão dos calendários. O tempo gasto pelo utilizador na inserção dos dados no sistema não está incluído.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 49 Esta representação é bastante útil e intuitiva para verificar, não só a hora de início dos setups e do processamento das operações, mas também o cumprimento das restrições tecnológicas (sequência de operações dentro da mesma ordem de fabrico e capacidade das máquinas). Esta parece ser uma boa forma de representar o resultado do planeamento, visto este sistema funcionar como apoio à decisão para o agente de planeamento. Rapidamente se consegue tirar ilações deste planeamento, que auxiliarão a construção dos calendários produtivos definitivos. O sistema desenvolvido permite ainda o cálculo de diversos avaliadores de desempenho. Os avaliadores apresentados na secção 4.4.5 são calculados e impressos automaticamente pelo sistema, após o botão “Avançar” presente na folha dos calendários ser selecionado (Figura 38). Figura 38 – Sistema desenvolvido: avaliadores de desempenho. Além de serem listados individualmente por ordem de fabrico ou por máquina, caso sejam relativos às ordens de fabrico ou relativos à ocupação do tempo das máquinas respetivamente, os avaliadores são também exibidos através do seu valor total e médio. Os valores máximos de cada avaliador são impressos a vermelho, para ser possível identificar mais rapidamente a ordem de fabrico ou máquina em causa. São ainda exibidos alguns avaliadores percentuais, entre os quais se destaca a percentagem de ordens de fabrico atrasadas. 5.2 Testes computacionais Por forma a analisar a performance do sistema de apoio à decisão desenvolvido, foram feitos testes ao seu funcionamento com dados de diversas ordens de fabrico da KTK. O planeamento da produção na KTK, além de não definir a hora de início de processamento das diversas operações, não calcula diretamente avaliadores de desempenho dos calendários obtidos. Isto leva a que uma eventual comparação entre os calendários gerados pelo sistema e os obtidos pela empresa seja pouco precisa e, de certa forma, pouco fundamentada. Contudo, a realização de testes computacionais com dados reais permite, por oposição ao que acontece quando se utilizam dados totalmente aleatórios, estudar o funcionamento do sistema no contexto a que se destina. Apesar de não ser possível comparar a qualidade da solução obtida pelo sistema com a obtida pela empresa, é possível analisar os potenciais ganhos em termos de tempo e flexibilidade que este sistema acarreta, fruto das diversas simulações feitas recorrendo às distintas regras de prioridade incorporadas no sistema. A análise das folhas de cálculo de planeamento da KTK, tal como a realizada no decurso do projeto, não permite apurar, de forma precisa, todos os parâmetros envolvidos num dado evento de planeamento. As datas mínimas de início de processamento das ordens de fabrico e
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 50 as datas da disponibilidade inicial das máquinas são exemplos disto mesmo, sendo-lhes por isso atribuído o valor 0 nas instâncias analisadas. A inexistência de tempos de setup para todas as possibilidades de consecutividade de operações, fez com que se tenha considerado para cada operação, independentemente da operação antecedente, sempre o mesmo tempo de setup. Este parâmetro é quantificado através da seguinte variável: tempo de setup que antecede a operação . Esta pode ser obtida através da seguinte forma: [ ] (78) A quantidade média de ordens de fabrico lançadas por mês na KTK é de cerca de 70. Caso o sistema desenvolvido seja utilizado regularmente numa base semanal, o número de ordens de fabrico em consideração deverá ser inferior a este. Contudo, as folhas de cálculo analisadas contêm informação acumulada, relativa a várias semanas. Dessa feita, a quantidade de dados aí existentes levou à criação de problemas de grande dimensão. A resolução de problemas com instâncias de grande dimensão, tal como os resolvidos no decurso dos testes de desempenho, permite testar a performance do sistema em circunstâncias rigorosas. É expectável que as circunstâncias da utilização do sistema em uso corrente sejam menos complexas e exigentes do que estas. Espera-se, por isso, que o processo de geração da solução nesse cenário seja mais célere que o verificado nas simulações. Foram resolvidos 4 problemas, pelas 7 distintas regras definidas, o que equivale à geração de 28 soluções. Os dados gerais dos problemas estão disponíveis na Tabela 4. Os testes foram executados num ambiente Windows Vista, CPU 2,00GHz, com 4,00GB de memória RAM. Tabela 4 – Dados gerais dos problemas analisados. Problema Máquinas Ordens de fabrico Operações Instância de dados13 P1 14 91 240 ANEXO A P2 13 81 204 ANEXO B P3 14 67 162 ANEXO C P4 13 63 154 ANEXO D Os avaliadores dos diversos calendários gerados pelo sistema com o desenrolar dos testes de desempenho são apresentados em anexo 14 . Independentemente do problema em análise, e da regra adotada, sabe-se que o sistema alcançou a solução em menos de 10 segundos, o que se afigura bastante positivo. As ilações a retirar destes testes são apresentadas na próxima secção. Aí, é feita uma análise de sensibilidade às diferentes regras, prestando especial atenção aos avaliadores relacionados com o atraso das ordens de fabrico. 13 A presença de datas devidas de entrega negativas nas instâncias de dados resulta de um, ou da combinação, de dois fatores. Primeiro, sabe-se que a data devida de entrega presente nas folhas de cálculo disponibilizadas consiste no prazo inicial pedido pelo cliente. No entanto, este mesmo prazo é depois reajustado pela KTK (alargado), consoante a sua disponibilidade de recursos, e acordado com o cliente. Na realidade não se verifica este atraso ainda antes do planeamento acontecer. Segundo, pode dar-se o caso da ordem de fabrico estar desde logo atrasada, ou perto disso, no início de um evento de planeamento, fruto do desequilíbrio carga-capacidade. Para não diminuir ainda mais as datas devidas de entrega a considerar nos testes, optou-se por não subtrair destas o tempo estimado necessário às operações e setups a realizar após as operações de maquinação das diversas ordens de fabrico. 14 Para cada avaliador indica-se a cor verde o valor que corresponde à regra (ou regras) com melhor desempenho.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 51 6 Conclusões e perspetivas de trabalho futuro No decurso deste projeto foi analisada a forma como o planeamento da produção é feito numa empresa industrial com um sistema de produção do tipo job shop. O planeamento em análise consiste na calendarização do processamento de um conjunto de ordens de fabrico. Cada ordem de fabrico corresponde a uma sequência pré-determinada de operações, cuja sequência deve ser garantida. Além disto, há ainda que garantir a limitação da capacidade das máquinas. Na KTK, apesar de serem impressos e afixados nas diversas máquinas os diagramas de Gantt, o planeamento é pensado de forma essencialmente manual. Embora o ERP da empresa tenha um módulo de planeamento da produção, o mesmo não está totalmente funcional e adaptado à realidade produtiva da empresa, fazendo com que recursos e tempo tenham que ser gastos nesta atividade. Para resolver este problema de planeamento, procedeu-se à definição do modelo matemático de programação linear. No entanto, a determinação da solução ótima para este modelo não é fácil dada a sua complexidade e dimensão, pelo que seria necessário a aquisição de software de otimização de que a empresa não dispõe. Mesmo assim, o tempo necessário à obtenção dessa solução ótima poderia não ser compatível com o tempo de resposta disponível. Por estes motivos, foi decidido definir um modelo heurístico, por forma a ser possível desenvolver um sistema de apoio à decisão para o efeito. O referido modelo baseia-se em regras de prioridade, visto ser um método de resolução por aproximação pouco complexo e facilmente entendido pelos utilizadores. Os agentes de planeamento podem, através deste método, ter uma maior perceção e compreensão do processo de tomada de decisão, aquando da seleção da operação seguinte a calendarizar. Foram definidas regras de prioridade que visam a data de conclusão e a data devida de entrega das ordens de fabrico. O facto de não haver dados relativos aos diferentes tempos de setup possíveis em função da sequência das operações realizadas numa determinada máquina, fez com que não fosse possível testar e aplicar outras regras que estivessem relacionadas com os setups. Por forma a averiguar as implicações das distintas regras de prioridade incorporadas, foram realizados testes computacionais a este sistema com dados do histórico de ordens de fabrico da empresa. Em qualquer um dos testes, verificou-se um tempo de execução de poucos segundos. Quando comparado com o sistema atual, este sistema permite um ganho imenso em termos de tempo e velocidade na resolução dos problemas. Relativamente ao atraso médio (e atraso total), sabe-se que a regra MDD é a que apresenta melhor desempenho nos 4 problemas analisados. São ainda obtidas, através desta regra, as menores percentagens de ordens de fabrico atrasadas nesses problemas. Quanto ao atraso máximo, a regra EDD consegue ter o melhor desempenho em 3 dos 4 problemas. A regra EDD baseia-se em informação relativa às datas devidas de entrega das ordens de fabrico, sendo por isso indicada para a diminuição do atraso máximo. A regra MDD, por oposição ao que acontece na EDD, vai sendo atualizada à medida que a calendarização é feita, o que a torna dinâmica. Esta regra tem em consideração o estado atual do problema. Caso se esteja a induzir uma ordem de fabrico em atraso, o seu valor é atualizado para o instante de tempo em que se prevê a sua conclusão; caso contrário, o seu valor é mantido na data devida de entrega. Nos problemas em análise, dado o elevado número de ordens de fabrico quando comparado com o número de máquinas (carga superior à capacidade), a regra MDD parece
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 52 ser mais indicada. É expectável que a data de conclusão das ordens de fabrico seja superior à sua data devida de entrega, à medida que a calendarização avança. A análise de regras orientadas a avaliadores de desempenho relacionados com a ocupação das máquinas fica desde logo condicionada, fruto do desconhecimento dos tempos setup dependentes da sequência de operações. Para todos os problemas em análise, independentemente da regra selecionada, o tempo médio e máximo gasto em setups é igual. Contudo, o tempo desocupado pode sofrer alterações consoante a regra adotada. Fruto destas variações, o tempo total improdutivo também apresenta diferentes valores consoante a regra selecionada. A regra ERD/FIFO é, em 3 dos 4 problemas, a que melhor resultado apresenta na minimização destes valores médios. A criação de novos parâmetros nas instâncias de dados, tais como a importância (ou peso) das ordens de fabrico ou a identificação do cliente das mesmas, possibilitaria a incorporação de novas regras de prioridade no sistema de apoio à decisão. Com a definição da importância das ordens de fabrico, poderiam ser modeladas regras que tivessem em conta o peso relativo de cada uma das ordens de fabrico. Essas regras poderiam ser adaptadas das atuais, bastando apenas multiplicar o seu valor pela importância relativa da ordem de fabrico. Da regra data de entrega modificada (MDD), por exemplo, poderia surgir uma nova regra, a data de entrega modificada ponderada. O mesmo pode ocorrer para as restantes regras agora definidas. A definição do parâmetro cliente associado às ordens de fabrico proporcionaria a possibilidade da incorporação de regras com bastante aderência à realidade produtiva da KTK. Poderiam ser definidas regras e, do mesmo modo, avaliadores de desempenho, que permitiriam entrar em consideração com o estado atual de todas as ordens de fabrico do mesmo cliente. Poderiam ser definidas regras, a partir das atuais, que tinham como objetivo reduzir os diversos avaliadores, não nos seus valores médios ou máximos, mas por cliente. A regra folga mínima (Min. Slack) poderia dar origem a uma nova regra, folga por cliente, por exemplo. Esta regra teria como principal objetivo a redução do atraso por cliente. Ao invés de ser selecionada a ordem de fabrico com menor folga, seria selecionada a ordem de fabrico que pertencesse ao cliente que tem a menor folga total. Como folga total de um cliente subentende-se a soma das folgas de todas as ordens de fabrico desse mesmo cliente. Por forma a aumentar a flexibilidade e adaptabilidade do sistema, poderiam ser incorporadas novas funcionalidades capazes de aumentar a partilha de informação e conhecimento entre o agente de planeamento e o sistema computadorizado. Uma possibilidade é a modelação e codificação de um novo algoritmo, que permitira ao agente de planeamento calendarizar as operações de uma máquina, a máquina crítica. O sistema ficaria responsável por calendarizar as restantes operações, consoante o planeamento já efetuado manualmente. A criticidade de uma máquina poderia ser medida, por exemplo, pela sua carga de trabalho. Para efeitos de planeamento da produção, os tempos de setup deveriam ter, por parte da empresa, outro tipo de tratamento. Dada a sua importância, quer pela sua dimensão temporal, quer pela sua elevada frequência de ocorrência, estes deveriam ser tratados de forma isolada. Numa abordagem deste tipo, o tempo de processamento das operações, apenas contemplaria o tempo de maquinação em série e o tempo de validação da primeira peça. Seria assim possível fazer uma análise isolada aos tempos e, naturalmente, aos custos de setup (perdas de produção). Por forma a tirar o máximo partido do sistema criado, seria interessante a KTK adotar uma abordagem na qual os tempos de setup sejam considerados dependentes da sequência de operações. A função planeamento da produção poderia fazer estimativas dos tempos de setup
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 53 para as diversas possibilidades de consecutividade entre operações. Estas poderiam basear-se no número e tipo de ferramentas que ficam alojadas na máquina entre operações. Contudo, dado o elevado número de ordens de fabrico em circulação, e a elevada natureza combinatória de um processo ao estilo job shop, esta tarefa não é de fácil e direta prossecução. Uma possibilidade é, numa primeira fase, fazer uma análise experimental a este tipo de abordagem. Em estudos académicos futuros poder-se-á utilizar software de otimização disponível na FEUP para a determinação da solução ótima do modelo de programação linear desenvolvido para a representação do problema real. Deste modo, poder-se-ia comparar, para algumas instâncias do problema real, as soluções obtidas pelo modelo heurístico (regras de prioridade) com as soluções ótimas dessas mesmas instâncias.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 60 [min] [min] [min] [min] 1 1 40 1 120 30 1 2992 9 150 1 2 26 1 120 31 1 600 7 60 2 1 50 1 120 32 1 3000 8 100 2 2 32 1 120 32 2 6000 9 65 3 1 35 1 120 33 1 2000 8 105 3 2 23 1 120 33 2 2000 10 55 4 1 31 1 120 34 1 579 8 45 4 2 46 1 90 34 2 1500 9 100 5 1 23 1 120 35 1 2075 8 55 5 2 38 1 90 35 2 1941 9 45 6 1 40 1 120 36 1 50 7 80 6 2 26 1 120 36 2 375 7 55 7 1 50 1 120 36 3 100 7 70 7 2 22 1 120 37 1 10 7 10 8 1 35 1 120 37 2 190 7 250 8 2 23 1 120 37 3 180 7 190 9 1 111 2 120 37 4 70 7 70 9 2 126 2 90 38 1 30 7 0 9 3 240 3 0 38 2 380 7 250 10 1 250 4 270 38 3 360 7 190 10 2 70 4 240 38 4 140 7 70 11 1 370 4 360 39 1 200 11 105 11 2 100 4 330 39 2 125 11 75 12 1 370 4 360 40 1 1500 2 130 12 2 100 4 330 40 2 1500 2 70 13 1 370 4 360 41 1 32 1 75 13 2 100 4 330 41 2 16 1 75 14 1 370 4 360 42 1 470 3 470 14 2 100 4 330 43 1 340 2 75 15 1 15 2 60 43 2 170 2 45 15 2 15 2 60 44 1 1064 2 135 16 1 3810 2 7530 44 2 164 2 135 16 2 2560 2 3765 45 1 45 2 60 17 1 50 1 120 45 2 100 2 55 17 2 26 1 60 45 3 150 5 0 18 1 242 3 60 46 1 200 3 200 19 1 480 5 0 47 1 1200 6 105 20 1 600 6 15 47 2 600 6 75 20 2 300 6 105 47 3 1200 6 130 20 3 300 6 75 47 4 1200 6 10 20 4 480 5 0 47 5 4800 8 90 20 5 420 7 100 48 1 440 1 70 21 1 720 5 0 48 2 330 1 55 22 1 840 5 0 48 3 3850 8 90 22 2 300 8 60 48 4 1320 12 70 23 1 300 6 15 48 5 660 12 40 23 2 300 6 150 49 1 3420 2 75 23 3 300 6 75 49 2 2280 2 75 23 4 300 6 120 49 3 1140 6 55 23 5 720 5 0 49 4 1710 3 75 23 6 360 7 50 50 1 3000 8 100 23 7 360 8 60 50 2 500 7 75 24 1 1400 7 100 51 1 300 12 135 24 2 560 7 55 51 2 330 12 150 24 3 1020 5 0 51 3 330 12 150 24 4 560 7 100 51 4 45 12 90 25 1 150 6 50 52 1 300 7 135 26 1 150 6 50 52 2 330 12 150 27 1 150 6 50 52 3 330 12 150 28 1 150 6 50 52 4 45 12 90 29 1 3000 9 150 53 1 140 7 150
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 61 [min] [min] [min] [min] 53 1 140 7 150 70 2 300 12 90 53 2 200 12 60 70 3 390 12 150 53 3 260 12 150 70 4 45 12 30 53 4 30 12 75 71 1 300 7 135 54 1 210 7 150 71 2 330 12 150 54 2 300 12 90 71 3 330 12 150 54 3 390 12 150 71 4 45 12 90 54 4 45 12 30 72 1 210 7 150 55 1 630 7 150 72 2 300 12 90 55 2 930 12 87 72 3 390 12 150 55 3 1170 12 150 72 4 45 12 30 55 4 135 12 75 73 1 300 7 135 56 1 630 7 150 73 2 330 12 150 56 2 930 12 87 73 3 330 12 150 56 3 1170 12 150 73 4 45 12 90 56 4 135 12 75 74 1 7898 6 100 57 1 315 7 150 74 2 4513 10 25 57 2 480 12 74 74 3 1880 7 55 57 3 585 12 150 74 4 4513 9 25 57 4 68 12 75 75 1 90 2 615 58 1 900 12 135 75 2 730 2 715 58 2 900 12 90 75 3 215 13 215 58 3 990 12 150 76 1 1140 3 210 58 4 135 12 75 76 2 2280 3 200 59 1 900 7 135 77 1 200 12 135 59 2 900 12 90 77 2 220 12 150 59 3 990 12 150 77 3 220 12 150 59 4 135 12 75 77 4 30 12 30 60 1 450 7 135 78 1 140 7 150 60 2 450 12 90 78 2 200 12 90 60 3 495 12 150 78 3 260 12 150 60 4 68 12 75 78 4 60 12 45 61 1 158 6 130 79 1 1500 2 130 61 2 158 6 100 79 2 1500 2 70 61 3 158 6 50 80 1 8000 11 190 62 1 158 6 130 81 1 2400 2 0 62 2 158 6 100 81 2 600 2 40 62 3 158 6 50 81 3 4800 7 135 63 1 158 6 130 82 1 1800 4 190 63 2 158 6 100 82 2 1200 14 130 63 3 158 6 50 83 1 155 1 0 64 1 158 6 130 83 2 2 1 40 64 2 158 6 100 84 1 30 1 150 64 3 158 6 50 84 2 18 1 130 65 1 158 6 130 85 1 18 13 130 65 2 158 6 100 86 1 155 1 0 65 3 158 6 50 86 2 2 1 40 66 1 180 6 130 87 1 155 1 0 66 2 180 6 100 87 2 2 1 40 66 3 180 6 50 88 1 40 1 150 67 1 180 6 130 88 2 16 1 40 67 2 180 6 100 89 1 10 1 150 67 3 180 6 50 89 2 4 1 40 68 1 630 7 150 90 1 5 1 150 68 2 930 12 87 90 2 3 1 140 68 3 1170 12 150 91 1 5 1 150 69 1 900 7 135 91 2 3 1 140 69 2 900 12 90 69 3 990 12 150 69 4 135 12 75 70 1 210 7 150
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 62 ERD/FIFO MDD EDD Min. Slack SSPT Slack/NOP CR Tempo de execução do sistema [s] 2,52 6,00 2,46 6,00 2,46 6,00 5,88 Número de decisões15 108 104 104 105 109 105 102 Número médio de operações selecionáveis por decisão15 7,76 7,97 7,97 8,02 7,21 8,01 8,02 [min] 10837,59 10827,86 11063,87 11355,86 76665,43 11831,45 12551,96 [min] 9071,87 9062,13 9298,14 9590,13 5899,70 10065,73 10786,23 [min] 10837,59 10827,86 11063,87 11355,86 7665,43 11831,45 12551,96 [min] 9587,48 9577,75 9813,76 10105,75 6415,32 10581,34 11301,85 [min] 34940,10 33272,41 33568,10 33582,07 34018,30 33590,81 33376,34 [min] 25352,62 23694,66 23754,34 23476,32 27602,98 23009,47 22074,49 [min] 42890,00 40680,00 40680,00 39234,00 38090,00 39234,00 38530,00 [min] 35090,00 37945,00 37945,00 37945,00 31720,00 37945,00 37945,00 [min] 42890,00 40680,00 40680,00 39234,00 38090,00 39234,00 38530,00 [min] 259750,00 238885,00 237658,00 237658,00 241295,00 237658,00 238438,00 [min] 259750,00 238885,00 237658,00 237658,00 241295,00 237658,00 238438,00 [min] 120000,00 111032,00 111411,00 111411,00 143370,00 112799,00 119016,00 Percentagem de ordens de fabrico atrasadas 43,96% 43,96% 46,15% 46,15% 43,96% 46,15% 46,15% [min] 2725,71 2725,71 2725,71 2725,71 2725,71 2725,71 2725,71 [min] 10200,57 11644,43 11464,07 11633,07 6158,07 11292,21 10564,57 [min] 12926,29 14370,14 14189,79 14358,79 8883,79 14017,93 13290,29 [min] 14050,00 14050,00 14050,00 14050,00 14050,00 14050,00 14050,00 [min] 31487,00 33830,00 33830,00 37467,00 19603,00 37467,00 37467,00 [min] 31832,00 34398,00 34398,00 37812,00 19683,00 37812,00 37812,00 Percentagem global de tempo total improdutivo 52,97% 55,60% 55,28% 55,58% 43,63% 54,98% 53,66% 15 Considera-se decisão a seleção, através de regras de prioridade, de uma próxima operação a calendarizar.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 63 ANEXO B: problema P2 1 2 3 4 5 6 7 8 9 10 11 12 13 [min] 0 0 0 0 0 0 0 0 0 0 0 0 0 [min] [min] [min] [min] 1 0 -115200 2 1 53 0 96480 4 1 2 0 -105120 2 1 54 0 64800 4 1 3 0 -105120 2 1 55 0 64800 4 1 4 0 -105120 1 1 56 0 86400 4 1 5 0 -105120 1 1 57 0 86400 4 1 6 0 -115200 2 1 58 0 86400 4 1 7 0 -105120 1 1 59 0 15840 3 1 8 0 17280 2 1 60 0 15840 2 1 9 0 25920 2 1 61 0 31680 3 1 10 0 36000 2 1 62 0 126720 3 1 11 0 -131040 1 1 63 0 126720 1 1 12 0 -36000 1 1 64 0 11520 2 1 13 0 4320 5 1 65 0 73440 2 1 14 0 -36000 1 1 66 0 82080 2 1 15 0 -36000 2 1 67 0 93600 2 1 16 0 4320 2 1 68 0 103680 2 1 17 0 4320 2 1 69 0 123840 2 1 18 0 -14400 1 1 70 0 56160 6 1 19 0 -14400 1 1 71 0 36000 2 1 20 0 -7200 2 1 72 0 36000 2 1 21 0 -7200 2 1 73 0 36000 2 1 22 0 -34560 1 1 74 0 36000 3 1 23 0 -4320 2 1 75 0 -135360 2 1 24 0 -4320 4 1 76 0 21600 1 1 25 0 46080 4 1 77 0 -120960 3 1 26 0 -54720 2 1 78 0 -145440 1 1 27 0 -54720 2 1 79 0 -135360 2 1 28 0 -204480 2 1 80 0 -125280 1 1 29 0 -256320 2 1 81 0 -125280 1 1 30 0 123840 3 1 31 0 25920 5 1 32 0 -20160 5 1 33 0 20160 4 1 34 0 -8640 1 1 35 0 5760 1 1 36 0 56160 4 1 37 0 5760 2 1 38 0 56160 3 1 39 0 56160 3 1 40 0 66240 4 1 41 0 76320 4 1 42 0 46080 2 1 43 0 56160 4 1 44 0 76320 4 1 45 0 36000 3 1 46 0 46080 3 1 47 0 56160 3 1 48 0 66240 3 1 49 0 76320 3 1 50 0 86400 3 1 51 0 96480 3 1 52 0 96480 4 1
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 64 [min] [min] [min] [min] 1 1 40 13 120 31 3 1210 2 120 1 2 26 13 120 31 4 1200 2 10 2 1 31 13 120 31 5 4830 8 60 2 2 46 13 90 32 1 450 12 60 3 1 23 13 120 32 2 340 12 45 3 2 38 13 90 32 3 3880 8 60 4 1 26 13 120 32 4 1330 7 60 5 1 22 13 120 32 5 670 7 30 6 1 35 13 120 33 1 3435 11 60 6 2 23 13 120 33 2 2295 10 60 7 1 240 6 0 33 3 1155 2 45 8 1 640 11 90 33 4 1725 6 60 8 2 370 11 60 34 1 1725 8 60 9 1 640 11 90 35 1 75 7 60 9 2 370 11 60 36 1 315 3 120 10 1 640 11 90 36 2 360 7 120 10 2 370 11 60 36 3 360 7 120 11 1 15 6 60 36 4 75 7 60 12 1 480 9 0 37 1 170 3 120 13 1 600 4 15 37 2 60 7 45 13 2 315 4 90 38 1 330 7 60 13 3 315 4 60 38 2 420 7 120 13 4 480 9 0 38 3 45 7 30 13 5 430 3 90 39 1 930 7 87 14 1 720 9 0 39 2 1200 7 120 15 1 840 9 0 39 3 165 7 45 15 2 330 8 30 40 1 660 3 120 16 1 720 9 0 40 2 930 7 87 16 2 330 8 30 40 3 1170 7 150 17 1 1020 9 0 40 4 165 7 45 17 2 570 3 90 41 1 345 3 120 18 1 3052 2 90 41 2 480 7 74 19 1 610 3 50 41 3 615 7 120 20 1 3010 8 90 41 4 98 7 45 20 2 6015 4 50 42 1 1020 7 120 21 1 2015 8 90 42 2 165 7 45 21 2 2010 5 45 43 1 915 3 120 22 1 579 8 45 43 2 930 7 60 23 1 2085 8 45 43 3 1020 7 120 23 2 1941 3 45 43 4 165 7 45 24 1 10 3 10 44 1 465 3 120 24 2 200 3 240 44 2 480 7 60 24 3 190 3 180 44 3 525 7 120 24 4 80 3 60 44 4 98 7 45 25 1 30 3 0 45 1 168 2 120 25 2 390 3 240 45 2 168 2 90 25 3 370 3 180 45 3 168 2 40 25 4 150 3 60 46 1 168 2 120 26 1 215 12 90 46 2 168 2 90 26 2 140 12 60 46 3 168 2 40 27 1 1510 10 120 47 1 168 2 120 27 2 1510 10 60 47 2 168 2 90 28 1 355 10 60 47 3 168 2 40 28 2 185 10 30 48 1 168 2 120 29 1 1079 10 120 48 2 168 2 90 29 2 179 10 120 48 3 168 2 40 30 1 45 10 60 49 1 168 2 120 30 2 110 10 45 49 2 168 2 90 30 3 150 9 0 49 3 168 2 40 31 1 1245 2 60 50 1 190 2 120 31 2 615 2 60 50 2 190 2 90
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 65 [min] [min] [min] [min] 50 3 190 2 40 70 6 760 3 1530 51 1 190 2 120 71 1 90 13 1550 51 2 190 2 90 71 2 74 13 120 51 3 190 2 40 72 1 90 13 120 52 1 660 3 120 72 2 46 13 120 52 2 930 7 87 73 1 51 13 60 52 3 1200 7 120 73 2 33 13 60 52 4 45 7 0 74 1 66 11 180 53 1 915 3 120 74 2 26 11 45 53 2 930 7 60 74 3 18 9 30 53 3 1020 7 120 75 1 1510 10 120 53 4 165 7 45 75 2 1510 10 60 54 1 240 3 120 76 1 8010 12 180 54 2 330 7 60 77 1 2460 10 120 54 3 420 7 12 77 2 615 10 45 54 4 45 7 30 77 3 4815 3 120 55 1 315 3 120 78 1 4815 1 120 55 2 360 7 120 79 1 155 13 0 55 3 360 7 120 79 2 12 13 30 55 4 75 7 60 80 1 26 13 30 56 1 240 3 120 81 1 14 13 30 56 2 330 7 60 56 3 420 7 120 56 4 45 7 30 57 1 315 3 120 57 2 360 7 120 57 3 360 7 120 57 4 75 7 60 58 1 7908 4 90 58 2 4523 5 60 58 3 1890 3 45 58 4 4528 4 10 59 1 90 10 615 59 2 730 10 715 59 3 215 1 215 60 1 40 13 120 60 2 26 13 120 61 1 480 11 15 61 2 3660 8 120 61 3 150 3 45 62 1 420 11 15 62 2 3060 8 120 62 3 130 3 45 63 1 30 7 30 64 1 170 3 120 64 2 60 7 45 65 1 370 11 360 65 2 100 11 330 66 1 410 11 390 66 2 110 11 360 67 1 410 11 390 67 2 110 11 360 68 1 410 11 390 68 2 110 11 360 69 1 119 12 180 69 2 134 12 120 70 1 100 3 30 70 2 1010 3 6060 70 3 760 3 6060 70 4 515 10 4560 70 5 510 3 6060
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 66 ERD/FIFO MDD EDD Min. Slack SSPT Slack/NOP CR Tempo de execução do sistema [s] 2,22 4,50 2,10 4,44 2,10 4,38 4,44 Número de decisões16 101 96 97 98 100 96 96 Número médio de operações selecionáveis por decisão16 6,49 6,43 6,51 6,81 7,16 6,71 6,90 [min] 10655,54 12180,32 13189,06 14490,01 11220,38 13480,41 14989,94 [min] 8777,58 10302,36 11311,10 12612,05 9342,42 11602,44 13111,98 [min] 10655,54 12180,32 13189,06 14490,01 11220,38 13480,41 14989,94 [min] 5553,32 7078,10 8086,84 9387,79 6118,16 8378,19 9887,72 [min] 33801,06 32038,55 32181,52 32652,09 33865,77 32507,27 32853,05 [min] 28247,74 24960,46 24094,68 23264,30 27747,61 24129,09 22965,33 [min] 43621,00 51101,00 54197,00 54097,00 44415,00 48734,00 53685,00 [min] 40011,00 48071,00 51167,00 51067,00 40760,00 45688,00 52650,00 [min] 43621,00 51101,00 54197,00 54097,00 44415,00 48734,00 53685,00 [min] 261648,00 258448,00 257818,00 257818,00 260858,00 257818,00 258448,00 [min] 261648,00 258448,00 257818,00 257818,00 260858,00 257818,00 258448,00 [min] 121887,00 121413,00 113697,00 115588,00 126660,00 115461,00 116916,00 Percentagem de ordens de fabrico atrasadas 44,44% 38,27% 41,98% 40,74% 44,44% 39,51% 45,68% [min] 3457,85 3457,85 3457,85 3457,85 3457,85 3457,85 3457,85 [min] 4511,69 8400,23 9483,54 8615,23 4696,00 8374,85 8008,08 [min] 7969,54 11858,08 12941,38 12073,08 8153,85 11832,69 11465,92 [min] 22800,00 22800,00 22800,00 22800,00 22800,00 22800,00 22800,00 [min] 17313,00 26567,00 29663,00 29144,00 16267,00 28738,00 28732,00 [min] 22800,00 29660,00 32756,00 32656,00 23594,00 29053,00 32244,00 Percentagem global de tempo total improdutivo 40,51% 50,33% 52,52% 50,78% 41,07% 50,28% 49,49% 16 Considera-se decisão a seleção, através de regras de prioridade, de uma próxima operação a calendarizar.
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 67 ANEXO C: problema P3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 [min] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [min] [min] [min] [min] 1 0 -115200 2 1 53 0 72000 2 1 2 0 -115200 2 1 54 0 83520 2 1 3 0 7200 2 1 55 0 93600 2 1 4 0 15840 2 1 56 0 113760 2 1 5 0 25920 2 1 57 0 46080 6 1 6 0 -141120 1 1 58 0 25920 2 1 7 0 -46080 1 1 59 0 25920 2 1 8 0 -5760 1 1 60 0 25920 2 1 9 0 -46080 1 1 61 0 25920 3 1 10 0 -46080 1 1 62 0 11520 2 1 11 0 -5760 2 1 63 0 11520 2 1 12 0 -5760 1 1 64 0 76320 2 1 13 0 -24480 1 1 65 0 -145440 2 1 14 0 -24480 1 1 66 0 -131040 3 1 15 0 -17280 2 1 67 0 -155520 1 1 16 0 -17280 2 1 17 0 -14400 1 1 18 0 -14400 4 1 19 0 36000 4 1 20 0 -64800 2 1 21 0 -214560 2 1 22 0 -266400 2 1 23 0 -266400 3 1 24 0 15840 5 1 25 0 10080 4 1 26 0 10080 3 1 27 0 46080 1 1 28 0 46080 1 1 29 0 56160 3 1 30 0 66240 3 1 31 0 36000 2 1 32 0 46080 3 1 33 0 46080 3 1 34 0 25920 3 1 35 0 36000 3 1 36 0 46080 3 1 37 0 56160 3 1 38 0 66240 3 1 39 0 76320 3 1 40 0 86400 3 1 41 0 86400 3 1 42 0 86400 3 1 43 0 54720 3 1 44 0 54720 3 1 45 0 76320 3 1 46 0 76320 3 1 47 0 76320 3 1 48 0 113760 4 1 49 0 531360 3 1 50 0 21600 3 1 51 0 116640 3 1 52 0 63360 2 1
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 68 [min] [min] [min] [min] 1 1 16 14 135 30 3 68 7 75 1 2 16 14 120 31 1 990 7 150 2 1 8 14 135 31 2 135 7 75 2 2 8 14 120 32 1 900 7 90 3 1 370 12 360 32 2 990 7 150 3 2 100 12 330 32 3 135 7 75 4 1 370 12 360 33 1 450 7 90 4 2 100 12 330 33 2 495 7 150 5 1 370 12 360 33 3 68 7 75 5 2 100 12 330 34 1 158 2 130 6 1 15 3 60 34 2 158 2 100 7 1 480 10 0 34 3 158 2 50 8 1 480 10 0 35 1 158 2 130 9 1 720 10 0 35 2 158 2 100 10 1 840 10 0 35 3 158 2 50 11 1 720 10 0 36 1 158 2 130 11 2 300 9 60 36 2 158 2 100 12 1 1020 10 0 36 3 158 2 50 13 1 2992 2 150 37 1 158 2 130 14 1 600 3 60 37 2 158 2 100 15 1 3000 8 100 37 3 158 2 50 15 2 6000 3 65 38 1 158 2 130 16 1 2000 8 105 38 2 158 2 100 16 2 2000 5 55 38 3 158 2 50 17 1 1941 3 45 39 1 180 2 130 18 1 10 3 10 39 2 180 2 100 18 2 190 3 240 39 3 180 2 50 18 3 180 3 190 40 1 180 2 130 18 4 70 3 70 40 2 180 2 100 19 1 30 3 0 40 3 180 2 50 19 2 380 3 250 41 1 930 2 87 19 3 360 3 190 41 2 1170 2 150 19 4 140 3 70 41 3 135 2 75 20 1 200 13 105 42 1 900 2 90 20 2 125 13 75 42 2 990 2 150 21 1 340 11 75 42 3 135 2 75 21 2 170 11 45 43 1 300 2 90 22 1 1064 11 135 43 2 390 2 150 22 2 164 11 135 43 3 45 2 30 23 1 45 11 60 44 1 330 2 150 23 2 100 11 55 44 2 330 2 150 23 3 150 10 0 44 3 45 2 90 24 1 1200 2 105 45 1 300 7 90 24 2 600 2 75 45 2 390 7 150 24 3 1200 2 130 45 3 45 7 30 24 4 1200 2 10 46 1 330 7 150 24 5 4800 8 90 46 2 390 7 150 25 1 3420 11 75 46 3 45 7 90 25 2 2280 11 75 47 1 330 7 150 25 3 1140 2 60 47 2 390 7 150 25 4 1710 6 75 47 3 45 7 90 26 1 330 7 150 48 1 7898 5 100 26 2 330 7 150 48 2 4513 5 70 26 3 45 7 90 48 3 1880 3 55 27 1 45 7 30 48 4 4513 4 25 28 1 135 7 75 49 1 90 11 615 29 1 930 7 87 49 2 730 11 715 29 2 1170 7 150 49 3 215 3 215 29 3 135 7 75 50 1 90 11 615 30 1 480 7 74 50 2 730 11 715 30 2 585 7 150 50 3 215 3 215
Desenvolvimento de um Sistema de Apoio à Decisão para o Planeamento da Produção 69 [min] [min] 51 1 300 12 135 51 2 3000 9 180 51 3 100 3 75 52 1 370 12 360 52 2 100 12 330 53 1 410 12 390 53 2 110 12 360 54 1 410 12 390 54 2 110 12 360 55 1 410 12 390 55 2 110 12 360 56 1 104 13 195 56 2 104 13 150 57 1 100 3 30 57 2 1010 3 6060 57 3 760 3 6060 57 4 415 11 4560 57 5 510 3 6060 57 6 760 3 1530 58 1 90 14 1550 58 2 54 14 140 59 1 60 14 150 59 2 36 14 130 60 1 36 14 75 60 2 18 14 75 61 1 56 14 190 61 2 16 14 55 61 3 18 10 30 62 1 565 4 0 62 2 280 4 0 63 1 800 11 195 63 2 200 11 135 64 1 2320 11 160 64 2 2320 11 160 65 1 1500 11 130 65 2 1500 11 70 66 1 2400 11 180 66 2 600 11 60 66 3 4800 3 135 67 1 155 1 4260