期刊名称：Relatórios de Pesquisa em Engenharia de Produção
电子版ISSN：1678-2399
出版年度：2008
卷号：8
出版社：Universidade Federal Fluminense (UFF)
摘要：This paper presents algorithms for single and parallel identical machine scheduling prob-lems. While the overall algorithm can be viewed as a branch-cut-and-price over a very largeextended formulation, a number of auxiliary techniques are necessary to make the columngeneration e.ective. Those techniques include a powerful fixing by reduced costs and a newproposed dual stabilization method. We tested the algorithms on instances of the classicalweighted tardiness problem. All the 375 single machine instances from the OR-Library, withup to 100 jobs, are solved to optimality in reasonable computational times and with minimalbranching, since the duality gaps are almost always reduced to zero in the ro ot node. Manymulti-machine instances with 40 and 50 jobs are also solved to optimality for the first time.The proposed algorithms and techniques are quite generic and can be used on several relatedscheduling problems
其他摘要：Este artigo apresenta algoritmos para problemas de escalonamento de uma m′aquina ou dem′aquinas id.enticas paralelas. O algoritmo geral pode ser visto como um branch-cut-and-pricesobre uma formula.c.ao extendida de grande tamanho, por′em algumas t′ecnicas auxiliares s.aonecess′arias para que a gera.c.ao de colunas seja efetiva. Essas t′ecnicas incluem uma poderosafixa.c.ao por custos reduzidos e um novo m′etodo de estabiliza.c.ao dual. Os algoritmos foramtestados em inst.ancias do cl′assico problema de escalonamento com p enalidades por atrasos po deradas. Todas as 375 inst.ancias de uma m′aquina da OR-Library foram resolvidas deforma ′otima em tempo computacional razo′avel e quase sem ramifica.c.oes, porque os gapsde dualidade s.ao quase sempre zero no n′o raiz da ′arvore de enumera.c.ao. Muitas inst.anciasmulti-m′aquinas com 40 e 50 tarefas puderam ser resolvidas pela primeira vez. Os algoritmose t′ecnicas propostos s.ao bastante gen′ericos e podem ser utilizados em v′arios outros tipos deproblemas de escalonamento
