Flow Shop

FLOW SHOP

MINIMIZATION OF MAKESPAN USING
JOHNSON’S RULE FOR

O
• flowshop contém tarefas disponíveis simultaneamente no tempo zero e ser processadas por duas máquinas dispostas em série com armazenamento ilimitado entre elas. Os tempos de processamento de todos os trabalhos são conhecidos com certeza. É necessário escalonar as tarefas nas máquinas, de modo a minimizar makespan . Este problema é resolvido por uma regra não-preemptiva de Johnson para a otimização do makespan no geral duas máquinas flowshop estático.

• é o resultado mais importante para o problema flowshop que agora se
Este
tornou um padrão na teoria do agendamento. A regra do Johnson para escalonamento de tarefas em duas máquinas flowshop é dado abaixo: Em um esquema ideal, tarefa precede a tarefa se:

•
Onde,
como,

é o tempo de processamento de tarefa na máquina 1 e é o tempo de processamento de tarefa na máquina 2. Da mesma forma, e são tempos de processamento da tarefa na máquina 1 e 2, respectivamente.
Os passos do algoritmo de Johnson para a construção de um esquema ideal pode ser resumido como se segue:

•= processamento da tarefa � na máquina 1.
= processamento da tarefa � na máquina 2.
Johnson’s Algorithm
Step 1: Forma set-I contendo todos os trabalhos com
Step 2: Forma set-II contendo todos os trabalhos com
The jobs with may be put in either set.
Step 3: Forma da sequência como se segue:
a) As tarefas no set-I serão as primeiras, em ordem crescente na (SPT)
b) As tarefas no set-II seguem ordem decrescente na (LPT). Os laços são quebrados de forma arbitrária.
Este tipo de escalonamento é referido como SPT (1) -LPT (2).

Exemplo:
•
Considere os seguintes dados apresenta uma instância do problema . Encontre valor ótimo do makespan usando a regra de Johnson.

5
1
1

2
4
4

3
3
3

6
5
5

7
2
2

•
Solution:
• Step 1: Of all jobs; 1 ≤ j ≤ 5 , only job has which belong to Set-I =
• Step 2: Jobs ,