Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Problema do Flowshop

0 votos
111 visitas
perguntada Dez 15, 2020 em Ciência da Computação por leonardocarvalho (21 pontos)  

O problema do Flowshop é um processo de agendamento onde cada processo i tem duas tarefas, A e B, que devem ser feitas em ordem A antes de B. Essas tarefas são feitas em processadores diferentes, onde a sequência escolhida do processo também deve ser a sequência em que elas ocorreriam individualmente.
Por exemplo, assuma que os tempos de execução para as tarefas A é de p = {3, 4, 8, 10}, e os tempos de execução das tarefas B é q = {6, 2, 9, 15}, onde i = {0, 1, 2, 3}. Se o processos são executados na ordem dada, então os tempos iniciais e finais de cada tarefa escolhida são dados por:

A imagem será apresentada aqui.

As linhas na tabela acima indicam, como função do tempo, as tarefas que são executadas com seus tempos de início e fim. Nós enfatizamos que B3 foi atrasado no tempo 11 por que B2 tinha sido completado por que A3 somente termina em 15.
O custo para esse agendamento é o tempo em que a última tarefa termina, que no exemplo acima é 40. O problema do Flowshop consiste em agendar processos que contenham o menor custo possível. Nós observamos que o custo geral é dado em três custos separados:

  1. O tempo de execução de todas as tarefas A, denotado c1.
  2. O tempo de execução da tarefa B final é executado, denotado c2.
  3. Qualquer atraso ocorrido para a tarefa B final, denotado c3.

No exemplo, c1 = 25, c2 = 15 e c3 = 0, e sua soma é de 40.
(Dynamic Programming - A Computation Tool (2007), pg. 61)

Compartilhe

1 Resposta

0 votos
respondida Dez 15, 2020 por leonardocarvalho (21 pontos)  
editado Dez 15, 2020 por leonardocarvalho

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:

  1. Verificamos qual dos processadores tem o menor tempo de tarefa.
  2. 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.
  3. 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.

comentou Dez 18, 2020 por Fernando Fellows (16 pontos)  
Olá, Leonardo. Achei muito interessante o uso do algoritmo de Johnson para alocação de tarefas dado o custo em A e B. Eu estou pensando se seria um bom teste ver qual estratégia é mais eficiente: se comparar o valor do custo de A e B do ítem i e depois observar se ele é o valor mínimo (em A ou B, a depender da comparação), ou fazer o caminho inverso, encontrar o primeiro mínimo em A e B e observar se o custoA e custoB para ver se o objeto vai para o final ou início da lista.
...