Primeiro, devemos conseguir imprimir na tela o formato de tabela apresentado pelo autor para mostrar o formato da otimização e comparar com o antigo. Isso é definido na função flowshop, que tem como argumentos arrayA e arrayB, indicando as tarefas do processador A e B. Após isso, temos duas listas, cada um com o formato final apresentado pelo autor em seus itens, com os tempos de inicio e fim de cada tarefa. Abaixo, há um array com os tempos finais, chamado timesA e timesB.
from random import randint
def flowshop(arrayA, arrayB):
runningTimeA, runningTimeB = [], []
timesA, timesB = [], []
for index, process in enumerate(arrayA):
if len(runningTimeA) == 0:
runningTimeA.append(f"A_{index+1}: 0-{process}")
oldTime = 0
else:
runningTimeA.append(f"A_{index+1}: {oldTime}-{process+oldTime}")
timesA.append(process+oldTime)
oldTime += process
oldTime = timesA[0]
runningTimeB.append(" "*len(runningTimeA[0]))
for index, process in enumerate(arrayB):
if timesA[index] > oldTime or index == 0:
runningTimeB.append(
f"B_{index+1}: {timesA[index]}-{process+timesA[index]}")
oldTime = process+timesA[index]
else:
runningTimeB.append(f"B_{index+1}: {oldTime}-{process+oldTime}")
oldTime += process
timesB.append(oldTime)
c1, c2 = sum(arrayA), arrayB[-1]
c3 = timesB[-2]-timesA[-1] if timesB[-2] > timesA[-1] else 0
print(f"{runningTimeA}\n{runningTimeB}")
print(f'''Custo total: {sum([c1, c2, c3])}\nCustos Individuais:
c1 (Tempo total para o primeiro processo): {c1}
c2 (Tempo para realizar o último processo de B): {c2}
c3 (Atraso entre o último processo de A e o ínicio do último processo de B): {c3}''')
O primeiro loop da função passa pelos elementos da primeira lista. Caso o tamanho do formato final que desejamos seja 0, iremos adicionar o número da tarefa do processo, junto com o ínicio em 0 e quanto tempo ele durou, definido pela variável process, e esse último tempo fica registrado na variável oldTime.
Caso já tenha sido rodado a primeira tarefa, iremos adicionar o índice dessa tarefa, porém, agora, ele irá iniciar a partir de oldTime, que é o tempo final de execução da última tarefa e sinalizar que irá terminar no tempo oldTime+process, que é o tempo com o qual ele começou somado com o tempo do processo atual.
Para o processador A é possível fazer isso já que seus tempos de execução só dependem de quando a última tarefa foi terminada.
Após gerar a lista do processador A, podemos começar a iniciar o de B. O tempo de início da primeira tarefa de B é determinado pelo tempo de fim da primeira tarefa de A, dessa forma, oldTime é igual ao primeiro tempo registrado em timesA.
No segundo loop, passamos por todos os elementos do processador B, agora com um condicional verificando se o tempo final de execução da tarefa de mesmo índice do processador A é maior que o tempo atual registrado. Caso seja, isso indica que o processador B terminou sua tarefa antes que A possa ter terminado, logo, ele tem que esperar que A termine e então iniciar sua próxima tarefa a partir do tempo final da execução de A.
O tempo de execução dessa tarefa de B, será o tempo que A demorou para iniciar sua última tarefa + o tempo dessa tarefa em B, com início no tempo de execução da tarefa i-1 de A.
Caso a tarefa atual de A já tenha sido realizada, o processador B irá registrar o término de sua última tarefa realizada. Por exemplo, na imagem acima, temos que a tarefa 1 de B só termina em 9, logo a tarefa 2 irá começar nesse tempo que já que o processo 2 de A já havia terminado no tempo 7.
Após a construção das listas de processamento, criamos c1, c2 e c3 usando a soma das tarefas de A, o tempo necessário para executar a última tarefa de B e o atraso que se decorreu entre o término da penúltima tarefa de B e a última tarefa de A, caso o valor do atraso seja negativo, o valor retornado é zero.
def optimalFlowshop(arrayA, arrayB):
# print(f"Original: {arrayA, arrayB}")
flowshop(arrayA, arrayB)
optimal_A, optimal_B = [0]*len(arrayA), [0]*len(arrayA)
optimal_A, optimal_B = findMinor(arrayA, arrayB, optimal_A, optimal_B)
# print(f"Original: {optimal_A, optimal_B}")
flowshop(optimal_A, optimal_B)
Na função optimalFlowshop temos o cálculo da otimização. Ele é feito usando o algoritmo de Johnson (ou regra de Johnson), que permite realizar quase sempre a melhor otimização possível dentro de um problema de agendamento de tarefas. Ele é feito da seguinte maneira:
- Verificamos qual dos processadores tem o menor tempo de tarefa.
- Se for o B, essa tarefa é colocada no final da lista de agendamento. Caso seja o processador A, ela é inserida no começo da lista.
- A tarefa i de ambos os processadores é excluída. Se não existir mais tarefas, termine o algoritmo. Caso contrário, procuramos pelo próximo menor valor entre os dois processadores com seus valores atualizados e volte para o primeiro passo.
Isso é representado pelo algoritmo acima. Primeiro é impresso os tempos originais dos dois processadores. Após isso, são criados duas listas vazias com 0 dentro, com o mesmo tamanho das listas dos processadores. E então é chamada a função auxiliar findMinor, que retorna os valores ótimos para os processadores A e B.
def findMinor(arrayA, arrayB, optimal_A, optimal_B, posA=0, posB=-1):
if len(arrayA) == 0:
return optimal_A, optimal_B
else:
valueA, valueB = min(arrayA), min(arrayB)
if valueA < valueB:
index = arrayA.index(valueA)
optimal_A[posA], optimal_B[posA] = arrayA[index], arrayB[index]
posA += 1
else:
index = arrayB.index(valueB)
optimal_A[posB], optimal_B[posB] = arrayA[index], arrayB[index]
posB -= 1
arrayA.remove(arrayA[index]), arrayB.remove(arrayB[index])
return findMinor(arrayA, arrayB, optimal_A, optimal_B, posA, posB)
Essa função procura o menor valor de A, depois o de B e os compara. Em seus argumentos, temos as listas originais de A e B, as listas ótimas e a posição inicial da lista A e B. Os dois últimos argumentos são iniciados dessa forma para que o algoritmo possa colocar os valores nas posições corretas, sendo -1 para A (que é atualizado quando o algoritmo entra na condição if) e 0 para a posição B (tambeḿ atualizado para a última posição de optimalA e optimalB.
Quando o valor de A é menor que B, coletamos o índice desse valor no arrayA e atualizamos as listas ótimas com seu valor correspondente em A e B, e a posição de A é atualizada para ser a próxima. Caso contrário, fazemos o mesmo processo mas o o índice do arrayB.
Após esse processo, removemos os valores de ambas as listas e fazemos uma chamada recursiva para findMinor procurar novamente qual o próximo menor valor.
myArrayA, myArrayB = [], []
for i in range(0, 996):
myArrayA.append(randint(1, 10000))
myArrayB.append(randint(1, 10000))
optimalFlowshop(myArrayA, myArrayB)
optimalFlowshop([3, 4, 8, 10], [6, 2, 9, 15])
No final do algoritmo, temos duas listas a serem testadas. O primeiro é de uma lista de valores aleatórios indo de 1 até 10000, ocupando 996 espaços dentro dessas listas. Caso maior, o algoritmo para devido a um maximum callstack da função recursiva.
Depois é utilizado o optimalFlowshop para as listas usadas como exemplo no exercício.