Estudo e análise do sequenciamento de tarefas de produção: job shop scheduling

Esta dissertação apresenta um estudo sobre os problemas de sequenciamento de tarefas de produção do tipo job shop scheduling. Os problemas de sequenciamento de tarefas de produção pretendem encontrar a melhor sequência para o processamento de uma lista de tarefas, o instante de início e término de cada tarefa e a afetação de máquinas para as tarefas. Entre estes, encontram-se os problemas com máquinas paralelas, os problemas job shop e flow shop. As medidas de desempenho mais comuns são o makespan (instante de término da execução de todas as tarefas), o tempo de fluxo total, a soma dos atrasos (tardiness), o atraso máximo, o número de tarefas que são completadas após a data limite, entre outros. Num problema do tipo job shop, as tarefas (jobs) consistem num conjunto de operações que têm de ser executadas numa máquina pré-determinada, obedecendo a um determinado sequenciamento com tempos pré-definidos. Estes ambientes permitem diferentes cenários de sequenciamento das tarefas. Normalmente, não são permitidas interrupções no processamento das tarefas (preemption) e pode ainda ser necessário considerar tempos de preparação dependentes da sequência (sequence dependent setup times) ou atribuir pesos (prioridades) diferentes em função da importância da tarefa ou do cliente. Pretende-se o estudo dos modelos matemáticos existentes para várias variantes dos problemas de sequenciamento de tarefas do tipo job shop e a comparação dos resultados das diversas medidas de desempenho da produção. Este trabalho contribui para demonstrar a importância que um bom sequenciamento da produção pode ter na sua eficiência e consequente impacto financeiro.

This paper presents a study on sequencing problems of the type job shop scheduling. Production sequencing problems aim to find the best sequence for processing a task list, the starting and ending instants of each task, and the machine allocation for tasks. Among these problems, there are the parallel machines, the job shop and flow shop problems. The most common performance measures are the makespan (completion time of all tasks), the total flow time, the tardiness (the sum of the delays), the maximum delay, the number of tasks that are completed after the deadline, among others. In a job shop problem, the tasks (jobs) are a set of operations that must be performed at a predetermined machine, obeying a certain sequence, with preset processing times. These environments allow for different task sequencing scenarios. Typically, the processing tasks are not allowed to be interrupted (preemption), and may also be worth considering sequence dependent setup times, or assign different weights to the jobs depending on the size of the task or priority of the customer. It is intended to study the existing mathematical models for the various variants of the job shop scheduling problems and to compare the results of the several performance measures. This work contributes to demonstrate the importance that a good sequencing of production tasks can have on their efficiency and resulting financial impact.