Majority of the studies in the scheduling literature is devoted to time based performance measures. In this thesis, we develop a model that considers monetary issues in single machine scheduling environments. We assume all the jobs should be completed by a common due date. An early revenue is earned if the completion time is before or on the due date, and a tardy revenue is gained if the job is completed after the due date. We consider restricted and unrestricted due date versions of the problem. Our objective is the maximization of the net present value of all revenues. We first investigate some special cases of the problem, and present polynomial time algorithms to solve them. Then, we develop branch and bound algorithms with lower and upper bounding mechanisms. Computational experiments have shown that the branch and bound algorithms can solve large-sized problems in reasonable times.

Neste trabalho abordamos o problema de programação de tarefas em um ambiente flow shop permutacional com mais de duas máquinas. Restringimos o estudo para o caso em que todas as tarefas têm uma data de entrega comum e restritiva, e onde o objetivo é minimizar a soma total dos adiantamentos e atrasos das tarefas em relação a tal data de entrega. É assumido também um ambiente estático e determinístico. Havendo soluções com o mesmo custo, preferimos aquelas que envolvem menos tempo de espera no buffer entre cada máquina. Devido à dificuldade de resolver o problema, mesmo para instâncias pequenas (o problema pertence à classe NP-difícil), apresentamos uma abordagem heurística para lidar com ele, a qual está baseada em busca local e faz uso de um algoritmo linear para atribuir datas de conclusão às tarefas na última máquina. Este algoritmo baseia-se em algumas propriedades analíticas inerentes às soluções ótimas. Além disso, foi desenvolvida uma formulação matemática do problema em programação linear inteira mista (PLIM) que vai permitir validar a eficácia da abordagem. Examinamos também o desempenho das heurísticas com testes padrões (benchmarks) e comparamos nossos resultados com outros obtidos na literatura. / In this work we approach the permutational flow shop scheduling problem with more than two machines. We restrict the study to the case where all the jobs have a common and restrictive due date, and where the objective is to minimize the total sum of the earliness and tardiness of jobs relative to the due date. A static and deterministic environment is also assumed. If there are solutions with the same cost, we prefer those that involve less buffer time between each machine. Due to the difficulty of solving the problem, even for small instances (the problem belongs to the NP-hard class), we present a heuristic approach to dealing with it, which is based on local search and makes use of a linear algorithm to assign conclusion times to the jobs on the last machine. This algorithm is based on some analytical properties inherent to optimal solutions. In addition, a mathematical formulation of the problem in mixed integer linear programming (MILP) was developed that will validate the effectiveness of the approach. We also examined the performance of our heuristics with benchmarks and compared our results with those obtained in the literature.

Neste trabalho abordamos o problema de programação de tarefas em um ambiente flow shop permutacional com mais de duas máquinas. Restringimos o estudo para o caso em que todas as tarefas têm uma data de entrega comum e restritiva, e onde o objetivo é minimizar a soma total dos adiantamentos e atrasos das tarefas em relação a tal data de entrega. É assumido também um ambiente estático e determinístico. Havendo soluções com o mesmo custo, preferimos aquelas que envolvem menos tempo de espera no buffer entre cada máquina. Devido à dificuldade de resolver o problema, mesmo para instâncias pequenas (o problema pertence à classe NP-difícil), apresentamos uma abordagem heurística para lidar com ele, a qual está baseada em busca local e faz uso de um algoritmo linear para atribuir datas de conclusão às tarefas na última máquina. Este algoritmo baseia-se em algumas propriedades analíticas inerentes às soluções ótimas. Além disso, foi desenvolvida uma formulação matemática do problema em programação linear inteira mista (PLIM) que vai permitir validar a eficácia da abordagem. Examinamos também o desempenho das heurísticas com testes padrões (benchmarks) e comparamos nossos resultados com outros obtidos na literatura. / In this work we approach the permutational flow shop scheduling problem with more than two machines. We restrict the study to the case where all the jobs have a common and restrictive due date, and where the objective is to minimize the total sum of the earliness and tardiness of jobs relative to the due date. A static and deterministic environment is also assumed. If there are solutions with the same cost, we prefer those that involve less buffer time between each machine. Due to the difficulty of solving the problem, even for small instances (the problem belongs to the NP-hard class), we present a heuristic approach to dealing with it, which is based on local search and makes use of a linear algorithm to assign conclusion times to the jobs on the last machine. This algorithm is based on some analytical properties inherent to optimal solutions. In addition, a mathematical formulation of the problem in mixed integer linear programming (MILP) was developed that will validate the effectiveness of the approach. We also examined the performance of our heuristics with benchmarks and compared our results with those obtained in the literature.