Em 1999, Petra Schuurman e Gerhard J. Woeginger publicaram o artigo "Algoritmos de aproximação de tempo polinomial para programação de máquinas: dez problemas em aberto" . Desde então, de acordo com o meu conhecimento, não foram exibidas análises que abordariam a mesma lista de problemas. Portanto, seria ótimo e útil se cada um de nós pudesse fazer um resumo desse tipo de alguns dos dez problemas em aberto e contribuir com isso aqui.
22
Respostas:
Minimização de Makespan em máquinas idênticas sob restrições de precedência
Aqui, o que vem à mente é o artigo deste ano de Ola Svensson "Programação condicionada por dureza condicional de precedência em máquinas idênticas". Em seu artigo, Ola prova que
Em 2008, foi publicado o artigo "Precedência restrita de programação em · óptima" que descreve um algoritmo paraP|prec,pj=1|Cmumax., Com o coeficiente de rendimento, indicado no seu título Isto melhora mediante algoritmo Coffman-Graham com ligado2-2(2−73p+1) P|prec,pj=1|Cmax , ondepé o número de máquinas.2−2p p
O artigo "Algoritmos de aproximação para agendamento de trabalhos com restrições de precedência em cadeia" por Jansen e Solis-Oba contém PTAS para e, como conseqüência, para P m | c h a i n s | C m a x como um caso especial do problema anterior.Qm|chains|Cmax Pm|chains|Cmax
Minimização de Makespan em máquinas uniformes sob restrições de precedência
Minimização de Makespan sob restrições de precedência com atrasos na comunicação
Minimização de Makespan em máquinas não relacionadas
Minimização de Makespan em lojas abertas
Minimização de Makespan em lojas de fluxo
Minimização de Makespan em lojas de trabalho
Tempo total de conclusão do trabalho sem restrições de precedência
Tempo total de conclusão do trabalho sob restrições de precedência
No "Teste ótimo de código longo com um bit livre", Bansal e Khot provaram que sim, mas assumindo uma nova variante da conjectura exclusiva dos jogos.
Critérios de tempo de fluxo
fonte
Esta página da web pode ter algumas informações de uso:
http://www.mathematik.uni-osnabrueck.de/research/OR/class/
fonte