Programação em maquinas paralelas não-relacionadas, sujeitas a divisão de tarefas

AUTOR(ES)

Marco Antonio Freitas do Egito

DATA DE PUBLICAÇÃO

1996

RESUMO

In this thesis new methods and procedures to solve the multimachine scheduling problem with early and tardy costs are proposed. The machines are unrelated, job splitting is allowed, the jobs may have different due dates and the changeover time to process a new job on a machine depends on the job previously processed on the same machine. This problem is new, hard to solve and no references have been found in respecialized literature. However, it has many applications in the manufacturing. Two linear mixed-integer programming models one stated when job splitting is allowed, as well as similarmodel is proposed for the case without job splitting. Since the problem is NP-hard, the models can oniy be used to solve small test problems. Based on the mixed-integer formulation, a tree search method is developed to be used in a Branch &Bound and in a Filtered Beam Search procedures. Two lower bounds are developed for the Branch &Bound and four bounds for the Filtered Beam Search. Some properties of the original problem and an efficient decomposition method to solve the LP model derived from the mixed-integer problem are presented. Many test problems with up to 120 jobs and 6 machines has been used to show the performance of the proposed methods

ASSUNTO(S)

programação heuristica otimização combinatoria planejamento da produção pesquisa operacional

Documentos Relacionados

• Algoritmo para o problema de seqüenciamento em máquinas paralelas não-relacionadas
• Um problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes de máquina e da sequência:: modelos e algoritmos exato.
• GRASP e Busca Tabu aplicados a problemas de programação de tarefas em maquinas paralelas
• Dimensionamento de lotes em maquinas paralelas
• Minimização do atraso medio na programação de maquinas paralelas : uma aplicação de busca tabu