FORMULA ES COM VARIáVEIS CONTENDO íNDICE DE TEMPO PARA O PROBLEMA DO FLOW SHOP EM DUAS MáQUINAS COM PENALIDADES POR ATRASO NAS TAREFAS

Muitos dos problemas de escalonamento situam-se na classe de complexidade NP - dificil, sendo o caso do problema deste estudo. Este trabalho tem por objetivo propor formulacoes de programacao inteira com variaveis contendo indice de tempo t para o problema de escalonamento deterministico Flow shop com duas maquinas onde existem penalidades por atraso nas tarefas, na notacao de tres campos tem-se: F2 | | ......... Sao apresentadas formulacoes com variaveis binarias ........ (que assumem valor unitario se a tarefa j finaliza seu processamento na maquina i no tempo t) e variaveis binarias ...... (que assumem valor unitario se a tarefa j tem seu processamento finalizado na segunda maquina no tempo t). Em testes elaborados com instancias de ate cinquenta tarefas, observou-se que a primeira formulacao obteve limites duais iniciais mais proximos do valor otimo da funcao objetivo, enquanto a segunda formulacao, mais compacta, obteve melhores tempos de resolucao.