MétodosSchedSPP20-05-10

MétodosSchedSPP20-05-10


DisciplinaPlanejamento e Controle da Produção1.692 materiais8.177 seguidores
Pré-visualização12 páginas
Average Flow Time
																																								Makespan
																																								Average Lateness
																																								Maximum Lateness
MOORE
		
		T A R E F A								A		B		C		D		E		F																		A						B		C		D		E		F
		Tempo Process. (pi)								9		7		3		4		8		6																		9						7		3		4		8		6																								CRITÉRIOS				Arbitrário				SPT		WSPT		EDD		EDD
		Data de Entrega (di)								22		17		16		13		16		9																		22						17		16		13		16		9																								STi = Atraso Total				30				34		47		31		34
																																																																												Max. Tardiness (Ti)				15				15		20		15		20
																																																																												Número de Tarefas com Atrasos (Ti)				3				4		3		3		2
																										F		D		C		E		B		A
																								Tempo de Fluxo		0		6		10		13		21		28		37
																								Data de Entrega				9		13		16		16		17		22
																																												F		D		C		B		A		E
																																										Tempo de Fluxo		0		6		10		13		20		29		37
																																										Data de Entrega				9		13		16		17		22		16
																																																														F		D		C		A		E		B
																																																												Tempo de Fluxo		0		6		10		13		22		30		37
																																																												Data de Entrega				9		13		16		22		16		17
		
		
		
		
		
		Tarefa		pi		di		wi		pi/wi		Ci		Fi		Li		Ei		Ti		Fi*wi								Tarefa		pi		di		wi																																								pi/wi
		F		6		9		4		1.50		6		6		-3		3		0		24								F		6		9		4																																								1.50
		D		4		13		5		0.80		10		10		-3		3		0		50								D		4		13		5																																								0.80
		C		3		16		5		0.60		13		13		-3		3		0		65								C		3		16		5																																								0.60
		A		9		22		7		1.29		22		22		0		0		0		154								A		9		22		7																																								2.00
		E		8		16		4		2.00		30		30		14		0		14		120								E		8		16		4																																								2.33
		B		7		17		3		2.33		37		37		20		0		20		111								B		7		17		3																																								1.29
		M É D I A										19.7		19.7		4.2		1.5		5.7		87.3
		M Á X I M O										37		37		20		3		20		154
																				34																		LEGENDA
		
																																								Geram valores iguais
		
																																								Average Flow Time
																																								Makespan
																																								Average Lateness
																																								Maximum Lateness
JOHNSON
		TAREFA		TEMPO PROCESSAMENTO
				MÁQUINA 1		MÁQUINA 2
		A		4		2
		B		7		7
		C		6		5
		
		
		TAREFA		MÁQUINA 1		MÁQUINA 2
		B		7		7
		C		6		5																																				F		D		C		B		A		E
		A		4		2																																		Tempo de Fluxo		0		6		10		13		20		29		37
																																								Data de Entrega				9		13		16		17		22		16
										Tempo de Fluxo®		0		7		13				17
										Máquina 1 ®		B		C		A
										Máquina 2 ®				B				C				A
										Tempo de Fluxo®		0		7				14				19		21
		
																																																																										pi/wi
																																																																										0.00
																																																																										0.00
																																																																										0.00
																																																																										0.00
																																																																										0.00
																																																																										0.00
3_MAQS
		TAREFA		TEMPO PROCESSAMENTO
				MÁQUINA 1		MÁQUINA 2		MÁQUINA 3
		A		18		9		16
		B		12		3		11
		C		10		2		20
		D		1		4		15
				MENOR = 1		MAIOR = 9		MENOR = 11
		
		TAREFA		MÁQUINA X		MÁQUINA Y
		A		18 + 9 = 27		9 + 16 = 25
		B		12 + 3 = 15		3 + 11 = 14
		C		10 + 2 = 12		2 + 20 = 22
		D		1 + 4 = 5		4 + 15 = 19
												0				1																				11																																				29																		38						41
										Máquina 1 ®		D				C																				A																																				B
										Máquina 2 ®						D																				C																																				A																								B
										Máquina 3 ®														D																														C																																								A																																B
										Tempo de Fluxo®		0												4																13														20																																								40								44																								56																						67
		TAREFA		MÁQUINA X		MÁQUINA Y
		A		27		25																																																																						pi/wi
		B		15		14																																																																						0.00
		C		12		22																																																																						0.00
		D		5		19																																																																						0.00
		TAREFA		MÁQUINA X		MÁQUINA Y																																																																						0
		D		5		19
		A		27		25																																																																						0
		B		15		14
		C		12		22
		TAREFA		MÁQUINA X		MÁQUINA Y
		D		5		19
		C		12		22
		A		27		25
		B		15		14
*
DEI - PUC/Rio
*
*
DEI - PUC/Rio
*
Heurística para reduzir o makespan em oficina de fluxo com mais de duas máquinas (não garante ótimo, em geral).
Usa o método de Johnson de forma heurística.
Cria várias programações para que se escolha a melhor
Programação em m máquinas: 
Método de Campbell , Dudek and Smith
DEI - PUC/Rio
*
DEI - PUC/Rio
*
*
DEI - PUC/Rio
*
Sejam n tarefas em m máquinas.
tji é o tempo de processamento da tarefa j na máquina i.
A cada estágio k = 1, 2, ..., m-1, um problema artificial de duas máquinas é criado de forma similar à do método de Johnson aplicado a três máquinas e resolvido gerando uma possível sequência. Dentre essas m-1, escolhe-se então uma sequência de menor makestpan.
Vejamos através de um exemplo:
Programação em m máquinas: 
Método de Campbell , Dudek and Smith
DEI - PUC/Rio
*
DEI - PUC/Rio
*
*
DEI - PUC/Rio
*
Etapa 1.
Construir um problema artificial de duas máquinas A e B com tA=t1 e tB=t4 e aplicar método de Johnson.
Etapa 1.
Sequência ótima da etapa 1
(2, 3, 1, 5, 4) makespan =37
Programação em m máquinas: 
Método de Campbell , Dudek and Smith
DEI - PUC/Rio
Plan1
		Tarefa		t1		t2		t3		t4
		1		7		4		3		8
		2		2		3		7		5
		3		4		1		2		7
		4		3		3		4		2
		5		9		2		6		3
		
		Tarefa		tA		tB
		1		7		8
		2		2		5
		3		4		7
		4		3		2
		5		9		3
Plan1
		Tarefa		t1		t2		t3		t4
		1		7		4		3		8
		2		2		3		7		5
		3		4		1		2		7
		4		3		3		4		2
		5		9		2		6		3
		
		Tarefa		tA		tB
		2		2		5
		3		4		7
		1		7		8
		5		9		3
		4		3		2
		
		Tarefa		t1		t2		t3		t4		C1		C2		C3		C4
		2		2		3		7		5		2		5		12		17
		3		4		1		2		7		6		7		14		24
		1		7		4		3		8		13		17		20		32
		5		9		2		6		3		22		24		30		35
		4		3		3		4		2		25		28		34		37
		
		Tarefa		t1		t2		t3		t4		C1		C2		C3		C4
		2		2		3		7		5		2		5		12		17
		3		4		1		2		7		6		7		14		24
		4		3		3		4		2		9		12		18		26
		1		7		4		3		8		16		20		23		34
		5		9		2		6		3		25		27		33		37
		
		Tarefa		t1		t2		t3		t4		C1		C2		C3		C4
		3		4		1		2		7		4		5		7		14
		2		2		3		7		5		6		9		16		21
		4		3		3		4		2		9		12		20		23
		1		7		4		3		8		16		20		23		31
		5		9		2		6		3		25		27		33		36
		
		Tarefa		t1		t2		t3		t4		C1		C2		C3		C4
		3		4		1		2		7		4		5		7		14
		2		2		3		7		5		6		9		16		21
		1		7		4		3		8		13		17		20		29
		5		9		2		6		3		22		24		30		33
		4		3		3		4		2		25		28		34		36
*
DEI - PUC/Rio
*
*
DEI - PUC/Rio
*
Etapa 2.
Construir um problema artificial de duas máquinas