Tarefa 5 - Problema de Progpagação e Sequenciamento - Pesquisa Operacional 2 - 2023-2

Universidade de São Paulo Escola de Engenharia de São Carlos Pesquisa Operacional II Problemas de Programação e Sequenciamento de Máquinas Máquina Única Os problemas de sequenciamento de máquinas determinam a ordem ou sequência de visitas de determinadas tarefas de modo a minimizar um determinado objetivo. O objetivo pode ser minimizar o makespan (M), minimizar o tempo total de conclusão, minimizar o tempo total de fluxo, minimizar o atraso total, minimizar a antecipação total, minimizar o número de tarefas atrasadas, minimizar o atraso máximo etc. Alguns objetivos importantes são os seguintes: Makespan: representa o primeiro momento em que todas as tarefas são concluídas. Se a tarefa j tem um tempo de conclusão Cj, makespan é dado por máximo Cj (j=1, 2, ..., n). O objetivo é minimizar o makespan. Tempo total de conclusão: representa uma medida do estoque de tarefa em andamento no sistema. O tempo total de conclusão é a soma dos tempos de conclusão e é dado por Σ_{j=1}^n Cj. O objetivo é minimizar o tempo total de conclusão ou o tempo médio de conclusão. Tempo total de fluxo: está intimamente associado ao tempo total de conclusão. Ele representa o tempo que uma tarefa está no sistema e também é um indicador do estoque no sistema. Se todos as tarefas estiverem disponíveis no tempo igual a zero, o tempo de fluxo é o mesmo que o tempo de conclusão. Se a tarefa j chega no tempo rj, o tempo total de fluxo é dado por Σ_{j=1}^n (Cj − rj). O objetivo é minimizar o tempo total de fluxo ou o tempo médio de fluxo. Total Lateness: Se a tarefa j tem uma data de vencimento Dj, então o lateness para a tarefa j é dado por Lj = Cj − Dj. A data de vencimento é a hora em que a tarefa deve ser entregue ao cliente (ou ao próximo estágio do processo de fabricação). O total lateness é dado por Σ_{j=1}^n Lj. O objetivo é minimizar o total lateness. Total Tardiness: O lateness de uma tarefa pode ser positivo ou negativo, dependendo se ele foi concluído antes da data de vencimento ou depois. Quando minimizamos o total lateness, os valores positivos e negativos podem se anular. Embora a conclusão antecipada não penalize indevidamente o sistema, os prazos de conclusão posteriores às datas de vencimento podem resultar em perda de vendas e multas contratuais. O lateness positivo em que a tarefa é concluída depois da data de vencimento é chamado de Tardiness. O tardiness Tj da tarefa j é dado por Tj = máx(0, Lj). O Total tardiness é dado por Σ_{j=1}^n Tj. O objetivo é minimizar o total tardiness. Earliness: Há situações em que terminar uma tarefa antes da data de vencimento não é desejável. Se o cliente seguir um sistema de fabricação Just in Time (JIT), as mercadorias não poderão ser enviadas antes das datas de vencimento. Estes permanecem no estoque de produtos acabados, aumentando os custos de estoque. Embora a antecipação deva ser minimizada, isso deve ser feito às custas do aumento do atraso, porque as penalidades por atraso são altas. A antecipação da tarefa j é definida como Ej = maximo (0, −Lj). Neste caso o objetivo seria minimizar a antecipação e o atraso total, que é dado por Σ_{j=1}^n (Ej + Tj). Algumas vezes damos pesos diferentes para a antecipação e atraso e minimizamos a função ponderada dada por Σ_{j=1}^n (αEj + βTj) onde α e β são os pesos dados para a antecipação e atraso (β > α). Número de tarefas atrasadas: Às vezes é necessário minimizar o número de tarefas atrasadas, especialmente quando as tarefas atrasadas vão para clientes diferentes. Esta é uma indicação de que vários clientes ficariam insatisfeitos e a organização perderia credibilidade. Definimos Nj = 1 se Tj > 0 e Nj = 0 caso contrário. Minimizamos o número de tarefas atrasadas n dado por Σ_{j=1}^n Nj. Atraso Máximo: Esta é uma medida importante quando as tarefas vão para o mesmo cliente. Se um subconjunto das tarefas for para o mesmo cliente, o trabalho mais atrasado decidirá a remessa. Além disso, o atraso máximo é um indicador do desempenho ruim do sistema. O atraso máximo é dado por máximo (Tj) e minimizamos o atraso máximo da tarefa j. Antes de formularmos problemas de programação da produção como problemas de programação inteira, foram apresentadas as expressões das funções de avaliação. Embora as formulações de programação inteira forneçam as soluções ótimas, elas se tornam intratáveis à medida que o tamanho do problema aumenta. Os solucionadores (softwares) são incapazes de fornecer soluções ótimas dentro de um tempo de computação razoável. Isso exigiu o desenvolvimento de algoritmos heurísticos que nem sempre garantem a solução ótimas. Os profissionais confiam nesses algoritmos heurísticos para fornecer soluções rápidas e boas. Neste assunto estudado também descreveremos algumas heurísticas relevantes para diferentes objetivos em diferentes configurações de problemas. Tarefa 1) Considere uma única máquina que processa cinco tarefas. As tarefas são nomeadas de J1 a J5. Os tempos de processamento são 10, 8, 6, 12 e 14 minutos. Os prazos de entrega (datas de vencimento) das cinco tarefas são 8, 16, 25, 30 e 40, respectivamente. Se você optar por seguir a sequência J2-J4-J3-J1-J5, encontre: a) O makespan; b) O tempo médio de conclusão; c) O tempo total de fluxo; d) O atraso total; e) A antecipação total; f) O número de trabalhos atrasados. Formulações para problemas de máquina única utilizando Programação Linear Tarefa 2) Tendo visto os cálculos relacionados às várias funções objetivo, agora podemos abordar esses problemas como problemas de otimização. Formular o problema de Scheduling da Tarefa 1 como um problema de Programação Linear e encontrar a solução ótima utilizando a ferramenta Solver do Excel para: a) Minimizar o atraso total; b) Minimizar Σ(Ej + Tj); c) Minimizar o atraso máximo; d) Minimizar o número de tarefas atrasadas; Sugestões: • Seja Sj a hora de início da tarefa j na máquina. O tempo de conclusão da tarefa j é dado por Cj = Sj + pj onde pj é o tempo de processamento da tarefa j. Sejam Ej e Tj a antecipação e o atraso respectivamente da tarefa j. Uma tarefa é adiantada se Dj > Cj e atrasado se Cj > Dj. Temos, portanto, a relação Tj = Ej = Cj − Dj e Ej, Tj ≥ 0. Também temos uma condição de que a máquina possa processar apenas uma tarefa por vez. Para um par de tarefas i e j, Si ≥ Cj ou Sj ≥ Ci. Isto é escrito como Sj + pj − Si ≤ M δij ≤ Si + pj − Sj ≤ M (1−δij) onde δij é binário. • Considerar M=1000.