Score
0
Best
-
Uma máquina de lavar, uma secadora e uma pilha de cargas. Escolha a ordem de lavagem que tire a última carga da secadora o mais cedo possível.
Toda carga tem de ser lavada primeiro e seca depois, e só existe uma máquina de cada tipo. A lavadora começa a carga seguinte assim que fica livre, mas a secadora só pode receber uma carga depois que ela sai da lavadora — enquanto espera, a secadora fica parada. A única coisa que você controla é a ordem.
Toque nas cargas na ordem em que quer lavá-las e as duas faixas se preenchem: a de cima é a lavadora, a de baixo a secadora, e os vãos da faixa de baixo são o tempo em que a secadora não faz nada. O número grande é quando a última carga finalmente sai. Toque de novo numa carga para tirá-la da fila.
Aperte para ligar quando estiver satisfeito com a ordem. Iguale o término mais curto que existe para aquela pilha e a rodada é sua. Se errar, perde um coração e a melhor ordem é mostrada, para você ver por onde o tempo escapou.
A cada três rodadas entra mais uma carga na pilha. Três erros encerram a partida, e o relógio também. Sua pontuação é o número de rodadas que você passa.
Isto é um flow shop de duas máquinas, um dos poucos problemas de programação em que a melhor resposta exata não só existe como pode ser obtida à mão. A regra chama-se regra de Johnson, é de 1954 e é curta o bastante para decorar. Separe as cargas em dois grupos: as cujo tempo de lavagem é menor ou igual ao de secagem, e as cuja lavagem é mais longa. Lave primeiro o primeiro grupo, da lavagem mais curta para a mais longa. Depois o segundo grupo, da secagem mais longa para a mais curta, de modo que a carga de secagem mais longa fique o mais tarde possível e a de secagem mais curta feche o dia.
O motivo se sente melhor do que se demonstra. A secadora é a máquina que encerra o dia, então tudo se resume a dar-lhe trabalho o quanto antes e deixar-lhe o mínimo no fim. Uma carga de lavagem rápida e secagem lenta é perfeita para começar: libera a lavadora quase de imediato e a secadora começa a trabalhar enquanto a lavadora ainda está ocupada. Uma carga de lavagem lenta e secagem rápida é perfeita para terminar: ninguém espera atrás dela e, quando enfim chega à secadora, acaba num instante. O resto se organiza sozinho a partir dessas duas pontas.
As medições dizem quanto a regra vale. Em milhares de pilhas geradas ao acaso, a ordem de Johnson atinge o término mais curto possível 100% das vezes — isso não é estatística, é o teorema. Aprender só metade da regra e ordenar apenas pelo tempo de lavagem chega a cerca de 48%. Lavar na ordem em que aparecem fica perto de 10%, quase o mesmo que embaralhar.
A armadilha que vale nomear é a jogada gulosa: a cada passo, acrescentar a carga que menos empurra o término para a frente. Parece a atitude cuidadosa e é a pior política medida aqui, acertando apenas cerca de 4%, nitidamente abaixo do acaso. Ela falha porque no início quase nada muda o término, então escolhe por um critério de desempate que não significa nada, e quando as escolhas passam a importar as cargas boas para o fecho já foram gastas. Ordene pela regra em vez de procurar passo a passo.