Che materia stai cercando?

Programmazione operativa della produzione Appunti scolastici Premium

Il presente testo costituisce una sintesi completa del corso di Programmazione Operativa della Produzione, di G. Passannanti. Il corso prevede nozioni teoriche di scheduling e algoritmi di programmazione della produzione e l’applicazione di alcuni di questi in linguaggio VBA su foglio elettronico . Per scrivere quanto segue si è preso spunto da appunti presi a lezione, materiale didattico... Vedi di più

Esame di Programmazione e gestione della produzione docente Prof. G. Passannanti

Anteprima

ESTRATTO DOCUMENTO

SPT – risultati N_job proc. time FT_average

19 5 464,04

25 5

21 8

30 9

39 9

46 9

50 9

13 10

22 10

24 11

8 12

3 12

35 12

48 13

31 14

20 15

44 15

5 17

23 21

45 21

34 22

1 23

12 24

41 25

15 27

33 27

4 28

42 28

2 29

43 29

11 30

26 31

38 31

28 32

7 32

17 34

47 34

6 36

10 37

27 37

32 38

36 40

40 42

16 42

14 44

18 46

29 46

9 51

49 51

37 51

26

WSPT – codice

Private Sub CommandButton2_Click()

ʹinizializzazione

Const n = 50, interv = 50, min_t = 5

Dim tl(n), seq(n, 3), ft(n), ft_w(n), w(n)

ʹgenerazione

For i = 1 To n

tl(i) = Int(Rnd * interv + min_t)

w(i) = Int(10 * Rnd + 1)

sum_w = sum_w + w(i)

Next i

For i = 1 To n

seq(i, 1) = i

seq(i, 2) = tl(i)

seq(i, 3) = w(i)

Next i

ʹordinamento WSPT

ft(0) = 0

For i = 1 To n ‐ 1

temp = seq(i, 2)

temp2 = seq(i, 3)

ind = i

n_part = seq(i, 1)

For j = i + 1 To n

If (temp / temp2) > (seq(j, 2) / seq(j, 3)) Then

ind = j

n_part = seq(j, 1)

temp = seq(j, 2)

temp2 = seq(j, 3)

End If

Next j

seq(ind, 2) = seq(i, 2): seq(i, 2) = temp: seq(ind, 3) = seq(i, 3): seq(i, 3) = temp2: seq(ind, 1) = seq(i, 1): seq(i, 1) =

n_part

ft(i) = seq(i, 2) + ft(i ‐ 1)

ft_w(i) = ft(i) * seq(i, 3)

Cells(i + 2, 7) = seq(i, 1): Cells(i + 2, 8) = seq(i, 2): Cells(i + 2, 9) = seq(i, 2) / seq(i, 3)

Next i

ft(n) = seq(n, 2) + ft(n ‐ 1)

ft_w(n) = ft(n) * seq(n, 3)

Cells(n + 2, 7) = seq(n, 1): Cells(n + 2, 8) = seq(n, 2): Cells(n + 2, 9) = seq(n, 2) / seq(n, 3)

For i = 1 To n

FT_av = FT_av + ft_w(i)

Next i

FT_av = FT_av / sum_w

Cells(3, 11) = FT_av

End Sub 27

WSPT – risultati N_job proc. time tl/w

47 7 0,875 FTw_average

9 7 1,4 439,6274

41 13 1,444444

5 6 1,5

20 6 1,5

42 15 1,5

10 15 1,666667

35 12 2

31 16 2,285714

37 23 2,555556

3 18 2,571429

36 16 2,666667

49 15 3

21 32 3,2

7 16 3,2

32 29 4,142857

8 17 4,25

11 34 4,25

28 26 4,333333

30 26 4,333333

40 35 4,375

24 38 4,75

39 39 4,875

46 10 5

48 31 5,166667

23 47 5,222222

50 42 5,25

26 29 5,8

2 48 6

22 31 6,2

34 20 6,666667

14 36 7,2

16 51 7,285714

29 45 7,5

43 8 8

1 27 9

18 28 9,333333

17 22 11

44 44 11

33 49 12,25

12 51 12,75

25 54 13,5

38 28 14

45 28 14

6 44 14,66667

4 17 17

27 39 19,5

15 53 26,5

19 54 27

13 32 32

28

EDD – codice

Private Sub CommandButton3_Click()

ʹinizializzazione

Const n = 50, interv = 50, min_t = 5, interv2 = 700, min_date = 650

Dim tl(n), seq(n, 3), l(n), DD(n), ft(n)

ʹgenerazione

For i = 1 To n

tl(i) = Int(Rnd * interv + min_t)

DD(i) = Int(Rnd * interv2 + min_date)

Next i

For i = 1 To n

seq(i, 1) = i

seq(i, 2) = tl(i)

seq(i, 3) = DD(i)

Next i

ʹordinamento EDD

ft(0) = 0

For i = 1 To n ‐ 1

temp = seq(i, 3)

ind = i

n_part = seq(i, 1)

For j = i + 1 To n

If temp > seq(j, 3) Then

ind = j

n_part = seq(j, 1)

temp = seq(j, 3)

temp2 = seq(j, 2)

End If

Next j

seq(ind, 2) = seq(i, 2): seq(i, 2) = temp2: seq(ind, 3) = seq(i, 3): seq(i, 3) = temp: seq(ind, 1) = seq(i, 1): seq(i, 1) =

n_part

ft(i) = seq(i, 2) + ft(i ‐ 1)

l(i) = ft(i) ‐ seq(i, 3)

Cells(i + 2, 15) = seq(i, 1): Cells(i + 2, 16) = seq(i, 2): Cells(i + 2, 17) = seq(i, 3): Cells(i + 2, 18) = l(i)

Next i

ft(n) = seq(n, 2) + ft(n ‐ 1)

l(n) = ft(n) ‐ seq(n, 3): Cells(n + 2, 18) = l(n)

Cells(n + 2, 15) = seq(n, 1): Cells(n + 2, 16) = seq(n, 2): Cells(n + 2, 17) = seq(n, 3)

l_max = l(1)

For i = 2 To n

If l_max < l(i) Then l_max = l(i)

Next i

Cells(3, 20) = l_max

End Sub 29

EDD – risultati N_job proc. time DD Lateness Late_max

22 38 660 ‐622 125

25 19 681 ‐624

48 18 688 ‐613

9 48 689 ‐566

40 26 718 ‐569

23 33 720 ‐538

29 18 762 ‐562

33 36 795 ‐559

18 50 808 ‐522

36 50 832 ‐496

15 18 845 ‐491

2 33 852 ‐465

13 33 858 ‐438

32 40 878 ‐418

10 52 904 ‐392

37 44 915 ‐359

26 19 917 ‐342

50 8 923 ‐340

28 53 930 ‐294

47 22 933 ‐275

31 25 938 ‐255

6 7 939 ‐249

44 50 951 ‐211

35 9 970 ‐221

46 30 974 ‐195

45 38 1001 ‐184

1 40 1023 ‐166

20 17 1023 ‐149

43 6 1030 ‐150

34 14 1058 ‐164

12 7 1064 ‐163

39 36 1089 ‐152

30 13 1102 ‐152

14 36 1103 ‐117

41 33 1136 ‐117

5 45 1146 ‐82

4 5 1182 ‐113

11 31 1186 ‐86

3 20 1192 ‐72

7 48 1203 ‐35

24 48 1209 7

16 46 1227 35

42 50 1234 78

38 19 1293 38

27 20 1313 38

8 23 1323 51

49 17 1335 56

19 39 1336 94

17 34 1340 124

21 10 1349 125

30

Algoritmo di Moore – codice

Private Sub CommandButton4_Click()

ʹinizializzazione

Const n = 50, interv = 50, min_t = 5, interv2 = 600, min_date = 600

Dim tl(n), seq(n, 3), l(n), DD(n), ft(n), R(n, 3)

ʹgenerazione

For i = 1 To n

tl(i) = Int(Rnd * interv + min_t)

DD(i) = Int(Rnd * interv2 + min_date)

Next i

For i = 1 To n

seq(i, 1) = i

seq(i, 2) = tl(i)

seq(i, 3) = DD(i)

Next i

ʹordinamento EDD + Moore

ft(0) = 0

For i = 1 To n ‐ 1

temp = seq(i, 3)

ind = i

n_part = seq(i, 1)

For j = i + 1 To n

If temp > seq(j, 3) Then

ind = j

n_part = seq(j, 1)

temp = seq(j, 3)

temp2 = seq(j, 2)

End If

Next j

seq(ind, 2) = seq(i, 2): seq(i, 2) = temp2: seq(ind, 3) = seq(i, 3): seq(i, 3) = temp: seq(ind, 1) = seq(i, 1): seq(i, 1) =

n_part

ft(i) = seq(i, 2) + ft(i ‐ 1)

l(i) = ft(i) ‐ seq(i, 3)

Next i

ft(n) = seq(n, 2) + ft(n ‐ 1)

l(n) = ft(n) ‐ seq(n, 3): Cells(n + 2, 18) = l(n)

k = 1

ʹMOORE

For i = 1 To n ‐ 1

If i = n ‐ k Then GoTo 1

If l(i) > 0 Then

temp = seq(1, 2)

ind = 1

For j = 1 To i

If temp < seq(j, 2) Then

temp = seq(j, 2)

ind = j

End If

Next j 31

R(k, 1) = seq(ind, 1): R(k, 2) = seq(ind, 2): R(k, 3) = seq(ind, 3)

For p = ind To n ‐ k

seq(p, 1) = seq(p + 1, 1): seq(p, 2) = seq(p + 1, 2): seq(p, 3) = seq(p + 1, 3)

Next p

For p = ind To n ‐ k

ft(p) = ft(p ‐ 1) + seq(p, 2)

l(p) = ft(p) ‐ seq(p, 3)

Next p

k = k + 1

i = i ‐ 1

End If

Next i

1

For i = n ‐ k + 1 To n

seq(i, 1) = R(i ‐ n + k, 1): seq(i, 2) = R(i ‐ n + k, 2): seq(i, 3) = R(i ‐ n + k, 3)

ft(i) = ft(i ‐ 1) + seq(i, 2)

l(i) = ft(i) ‐ seq(i, 3)

If l(i) > 0 Then

N_r = N_r + 1

End If

Next i

For i = 1 To n

Cells(i + 2, 23) = seq(i, 1): Cells(i + 2, 24) = seq(i, 2): Cells(i + 2, 25) = seq(i, 3): Cells(i + 2, 26) = l(i)

Next i

Cells(3, 28) = N_r

End Sub

Algoritmo di Moore – risultati N_job_rit

4

proc.

N_job DD Lateness

time

8 18 633 ‐615

48 32 648 ‐598

25 46 649 ‐553

39 17 653 ‐540

33 21 657 ‐523

21 8 663 ‐521

22 21 676 ‐513

14 32 693 ‐498

34 34 701 ‐472

32 29 724 ‐466

20 5 726 ‐463

36 27 763 ‐473

41 44 778 ‐444

40 6 793 ‐453

32

43 17 804 ‐447

27 27 814 ‐430

10 8 834 ‐442

16 30 834 ‐412

7 22 842 ‐398

49 36 846 ‐366

4 50 858 ‐328

31 25 877 ‐322

6 30 877 ‐292

12 12 884 ‐287

42 16 888 ‐275

44 7 889 ‐269

11 23 893 ‐250

5 38 901 ‐220

29 51 918 ‐186

23 5 922 ‐185

24 37 926 ‐152

3 6 926 ‐146

13 6 977 ‐191

15 51 992 ‐155

38 51 1004 ‐116

26 14 1007 ‐105

1 33 1016 ‐81

28 12 1022 ‐75

37 12 1050 ‐91

18 12 1052 ‐81

46 34 1052 ‐47

30 9 1054 ‐40

17 10 1070 ‐46

19 10 1099 ‐65

2 10 1100 ‐56

45 10 1118 ‐64

50 53 668 439

35 51 658 500

47 51 798 411

1209

Macchine in parallelo (no preemption allowed) – codice

Private Sub CommandButton5_Click()

ʹinizializzazione

Const n = 50, m = 4, interv = 50, min_t = 5

Dim seq(n, 2), ft(n), tl(n), C(m), tempi(n, 2), mac(n)

ʹgenerazione

For i = 1 To n

tl(i) = Int(Rnd * interv + min_t) 33

Next i

For i = 1 To n

seq(i, 1) = i

seq(i, 2) = tl(i)

Cells(i + 2, 30) = i: Cells(i + 2, 31) = tl(i)

Next i

ʹordinamento LPT

For i = 1 To n ‐ 1

temp = seq(i, 2)

ind = i

n_part = seq(i, 1)

For j = i + 1 To n

If temp < seq(j, 2) Then

ind = j

n_part = seq(j, 1)

temp = seq(j, 2)

End If

Next j

seq(ind, 2) = seq(i, 2): seq(i, 2) = temp: seq(ind, 1) = seq(i, 1): seq(i, 1) = n_part

Next i

ʹCarico sulle macchine

For i = 1 To m

mac(seq(i, 1)) = i

tempi(seq(i, 1), 1) = 0

tempi(seq(i, 1), 2) = seq(i, 2)

C(i) = seq(i, 2)

Cells(seq(i, 1) + 2, 32) = tempi(seq(i, 1), 1): Cells(seq(i, 1) + 2, 33) = tempi(seq(i, 1), 2): Cells(seq(i, 1) + 2, 34) =

mac(seq(i, 1))

Next i

For i = m + 1 To n

ind = 1

For j = 2 To m

If C(ind) > C(j) Then ind = j

Next j

mac(seq(i, 1)) = ind

tempi(seq(i, 1), 1) = C(ind)

C(ind) = C(ind) + seq(i, 2)

tempi(seq(i, 1), 2) = C(ind)

Cells(seq(i, 1) + 2, 32) = tempi(seq(i, 1), 1): Cells(seq(i, 1) + 2, 33) = tempi(seq(i, 1), 2): Cells(seq(i, 1) + 2, 34) =

mac(seq(i, 1))

Next i

C_max = C(1)

For i = 2 To m

If C_max < C(i) Then C_max = C(i)

Next i

Cells(3, 36) = C_max

End Sub

34

Macchine in parallelo (no preemption allowed) – risultati

N_job proc. time T_start T_end N_mac C_max

1 23 249 272 3 323

2 29 196 225 2

3 12 289 301 2

4 28 196 224 4

5 17 272 289 2

6 36 130 166 3

7 32 132 164 4

8 12 287 299 3

9 51 0 51 1

10 37 95 132 1

11 30 166 196 3

12 24 225 249 3

13 10 300 310 1

14 44 51 95 1

15 27 225 252 1

16 42 51 93 2

17 34 131 165 2

18 46 0 46 4

19 5 318 323 3

20 15 272 287 3

21 8 310 318 3

22 10 299 309 4

23 21 252 273 1

24 11 299 310 3

25 5 318 323 4

26 31 165 196 2

27 37 93 130 3

28 32 164 196 4

29 46 46 92 4

30 9 310 319 1

31 14 273 287 1

32 38 93 131 2

33 27 224 251 4

34 22 250 272 2

35 12 287 299 4

36 40 92 132 4

37 51 0 51 2

38 31 166 197 1

39 9 301 310 2

40 42 51 93 3

41 25 225 250 2

42 28 197 225 1

43 29 196 225 3

44 15 272 287 4

45 21 251 272 4

46 9 309 318 4

47 34 132 166 1

48 13 287 300 1

49 51 0 51 3

50 9 310 319 2 35

Applicazione dell’algoritmo di Johnson, con l’utilizzo dell’indice p. Anche in questo caso, come in tutti quelli

successivi, i dati di input sono generati in modo random. In questo caso l’algoritmo non prevede il calcolo del

makespan; si è provveduto ad implementare unicamente la procedura di sorting che, come sappiamo, è una

procedura esatta.

Codice

Private Sub CommandButton1_Click()

Const n = 50, interv = 50, min_tl = 5

Dim tl1(n), tl2(n), seq(n, 4), p(n)

For i = 1 To n

tl1(i) = Int(Rnd * interv + min_tl)

tl2(i) = Int(Rnd * interv + min_tl)

Next i

For i = 1 To n

If tl1(i) > tl2(i) Then

den = tl2(i)

num = 1

Else

den = tl1(i)

num = ‐1

End If

If tl1(i) = tl2(i) Then

p(i) = 0

GoTo 1

End If

p(i) = num / den

1

seq(i, 1) = i: seq(i, 2) = tl1(i): seq(i, 3) = tl2(i): seq(i, 4) = p(i)

Next i

For i = 1 To n ‐ 1

For j = i + 1 To n

If seq(i, 4) > seq(j, 4) Then

temp = seq(i, 1): seq(i, 1) = seq(j, 1): seq(j, 1) = temp

temp = seq(i, 2): seq(i, 2) = seq(j, 2): seq(j, 2) = temp

temp = seq(i, 3): seq(i, 3) = seq(j, 3): seq(j, 3) = temp

temp = seq(i, 4): seq(i, 4) = seq(j, 4): seq(j, 4) = temp

End If

Next j

Cells(i + 2, 1) = seq(i, 1): Cells(i + 2, 2) = seq(i, 2): Cells(i + 2, 3) = seq(i, 3): Cells(i + 2, 4) = seq(i, 4)

Next i

Cells(n + 2, 1) = seq(n, 1): Cells(n + 2, 2) = seq(n, 2): Cells(n + 2, 3) = seq(n, 3): Cells(n + 2, 4) = seq(n, 4)

End Sub

36

Risultati

N_job tl(1) tl(2) p

30 8 25 ‐0,125

12 10 18 ‐0,1

7 11 52 ‐0,09091

33 12 34 ‐0,08333

17 15 27 ‐0,06667

18 16 48 ‐0,0625

47 16 52 ‐0,0625

41 17 23 ‐0,05882

43 18 34 ‐0,05556

27 18 40 ‐0,05556

32 20 44 ‐0,05

31 21 40 ‐0,04762

16 21 43 ‐0,04762

20 24 48 ‐0,04167

42 24 31 ‐0,04167

28 25 45 ‐0,04

40 26 42 ‐0,03846

49 29 43 ‐0,03448

2 30 42 ‐0,03333

21 34 51 ‐0,02941

37 34 50 ‐0,02941

13 37 47 ‐0,02703

46 37 50 ‐0,02703

5 38 50 ‐0,02632

26 42 47 ‐0,02381

10 13 13 0

4 53 45 0,022222

8 44 39 0,025641

36 54 36 0,027778

48 47 27 0,037037

29 42 26 0,038462

11 30 25 0,04

6 48 25 0,04

50 46 24 0,041667

19 35 23 0,043478

15 49 23 0,043478

22 30 21 0,047619

3 45 21 0,047619

23 48 17 0,058824

34 52 17 0,058824

38 33 17 0,058824

14 29 14 0,071429

24 17 13 0,076923

45 49 10 0,1

35 51 10 0,1

39 48 8 0,125

44 15 8 0,125

1 44 7 0,142857

25 22 5 0,2

9 25 5 0,2 37

In questo paragrafo mostreremo gli algoritmi euristici costruttivi visti nel Capitolo 4. In questo caso i dati di

input sono generati casualmente, ma la generazione pseudo‐casuale permette di fare in modo che siano gli

stessi per tutti i diversi algoritmi, in modo da confrontare le soluzioni ottenute in termini di makespan. Come

annunciato nel Capitolo 4, la soluzione migliore si ottiene con il NEH, per il quale, tuttavia, il codice risulta

notevolmente più complesso.

CDS – Codice

Private Sub CommandButton1_Click()

Const N = 20, interv = 50, min_tl = 5, M = 6

Dim tl1(N), tl2(N), seq(N, 4), p(N), tl(N, M), TI(N, M), TF(N, M)

For i = 1 To N

For j = 1 To M

tl(i, j) = Int(Rnd * interv + min_tl)

Next j

Next i

For H = 1 To M ‐ 1

ʹtempi fittizzi secondo CDS

For i = 1 To N

tl1(i) = 0: tl2(i) = 0

For T = 1 To H

tl1(i) = tl1(i) + tl(i, T)

Next T

For T = H + 1 To M

tl2(i) = tl2(i) + tl(i, T)

Next T

Next i

ʹJohnson

For i = 1 To N

If tl1(i) > tl2(i) Then

den = tl2(i)

num = 1

Else

den = tl1(i)

num = ‐1

End If

If tl1(i) = tl2(i) Then

p(i) = 0

GoTo 1

End If

p(i) = num / den

1

seq(i, 1) = i: seq(i, 2) = tl1(i): seq(i, 3) = tl2(i): seq(i, 4) = p(i)

Next i

38

For i = 1 To N ‐ 1

For j = i + 1 To N

If seq(i, 4) > seq(j, 4) Then

temp = seq(i, 1): seq(i, 1) = seq(j, 1): seq(j, 1) = temp

temp = seq(i, 2): seq(i, 2) = seq(j, 2): seq(j, 2) = temp

temp = seq(i, 3): seq(i, 3) = seq(j, 3): seq(j, 3) = temp

temp = seq(i, 4): seq(i, 4) = seq(j, 4): seq(j, 4) = temp

End If

Next j

Cells(i + 2, H + colonna) = seq(i, 1)

Next i

Cells(N + 2, H + colonna) = seq(N, 1)

ʹCalcolo di Cmax per lo schedule trovato

TI(1, 1) = 0: TF(1, 1) = tl(seq(1, 1), 1)

For j = 2 To M

TI(1, j) = TF(1, j ‐ 1)

TF(1, j) = TI(1, j) + tl(seq(1, 1), j)

Next j

For i = 2 To N

TI(i, 1) = TF(i ‐ 1, 1)

TF(i, 1) = TI(i, 1) + tl(seq(i, 1), 1)

Next i

For i = 2 To N

For j = 2 To M

If TF(i, j ‐ 1) > TF(i ‐ 1, j) Then

temp = TF(i, j ‐ 1)

Else

temp = TF(i ‐ 1, j)

End If

TI(i, j) = temp

TF(i, j) = TI(i, j) + tl(seq(i, 1), j)

Next j

Next i

C_max = TF(N, M)

Cells(N + 4, H + colonna) = C_max

colonna = colonna + 1

Next H

End Sub 39

CDS – Risultati

CDS (Petrov)

Sol 1 Sol 2 Sol 3 Sol 4 Sol 5

2 9 9 9 7

15 14 12 14 9

18 15 18 13 14

12 18 14 12 8

17 8 13 15 19

9 5 15 6 1

11 12 6 7 10

14 2 3 1 13

20 11 7 3 4

5 16 4 8 15

16 13 1 19 17

8 20 19 17 2

7 17 17 11 12

1 1 5 10 5

13 4 11 18 6

6 10 2 4 11

3 19 20 5 20

19 6 8 2 18

4 3 10 16 3

10 7 16 20 16

C_max C_max C_max C_max C_max

838 832 821 808 945

Rapid Access – Codice

Private Sub CommandButton2_Click()

Const N = 20, interv = 50, min_tl = 5, M = 6

Dim tl1(N), tl2(N), seq(N, 4), p(N), tl(N, M), TI(N, M), TF(N, M)

For i = 1 To N

For j = 1 To M

tl(i, j) = Int(Rnd * interv + min_tl)

Next j

Next i

ʹtempi fittizzi secondo Dannenbring

For i = 1 To N

tl1(i) = 0: tl2(i) = 0

For T = 1 To M

tl1(i) = tl1(i) + (M ‐ T + 1) * tl(i, T)

tl2(i) = tl2(i) + (T) * tl(i, T)

Next T

40

Next i

(da qui in poi il codice è identico al CDS, ovvero si prosegue con l’applicazione dell’algoritmo di

Johnson ed il calcolo del makespan)

End Sub

Rapid Access – Risultati

Dannenbring

Soluzione 9

18

8

12

15

14

13

6

3

7

1

19

4

2

11

17

5

20

10

16

C_max 807

Algoritmo di Grasso – Codice

Private Sub CommandButton3_Click()

Const N = 20, interv = 50, min_tl = 5, M = 6

Dim tl1(N), tl2(N), seq(N, 4), p(N), tl(N, M), TI(N, M), TF(N, M)

For i = 1 To N

For j = 1 To M

tl(i, j) = Int(Rnd * interv + min_tl)

Next j

Next i

For H = 1 To M 41

ʹtempi fittizzi secondo Grasso

For i = 1 To N

tl1(i) = 0: tl2(i) = 0

For T = 1 To M ‐ H + 1

tl1(i) = tl1(i) + (M ‐ H + 2 ‐ T) * tl(i, T)

Next T

For T = H To M

tl2(i) = tl2(i) + tl(i, T) * (T ‐ H + 1)

Next T

Next i

(da qui in poi il codice è identico al CDS, ovvero si prosegue con l’applicazione dell’algoritmo di

Johnson ed il calcolo del makespan per la configurazione corrente)

Next H

End Sub

Algoritmo di Grasso – Risultati

MSP1 ‐ Algoritmo di Grasso

Sol 1 Sol 2 Sol 3 Sol 4 Sol 5 Sol 6

9 9 9 9 15 2

18 18 18 18 9 15

8 12 12 12 18 12

12 8 14 14 2 17

15 14 8 15 14 9

14 15 15 8 12 14

13 13 13 13 8 8

6 6 6 7 7 7

3 7 7 6 13 1

7 3 1 1 1 18

1 1 3 19 19 19

19 19 19 3 10 10

4 4 4 4 6 13

2 2 11 17 17 4

11 11 2 10 4 5

17 17 17 11 11 6

5 5 5 2 3 11

20 20 10 5 5 20

10 10 20 20 20 3

16 16 16 16 16 16

C_max C_max C_max C_max C_max C_max

807 790 797 822 801 817

(Dannenbring)

42

Palmer – Codice

Private Sub CommandButton4_Click()

Const N = 20, interv = 50, min_tl = 5, M = 6

Dim seq(N), s(N), tl(N, M), TI(N, M), TF(N, M)

For i = 1 To N

For j = 1 To M

tl(i, j) = Int(Rnd * interv + min_tl)

Next j

Next i

ʹPalmer

For i = 1 To N

For j = 1 To M

s(i) = s(i) ‐ (tl(i, j) * (M ‐ (2 * j) + 1) / 2)

Next j

seq(i) = i ʹinizializzo la sequenza iniziale

Next i

For i = 1 To N ‐ 1

For j = i + 1 To N

If s(i) > s(j) Then

temp = seq(i): seq(i) = seq(j): seq(j) = temp

temp = s(i): s(i) = s(j): s(j) = temp

End If

Next j

Cells(i + 2, 28) = seq(i)

Next i

Cells(N + 2, 28) = seq(N)

ʹCalcolo di Cmax per lo schedule trovato

TI(1, 1) = 0: TF(1, 1) = tl(seq(1), 1)

For j = 2 To M

TI(1, j) = TF(1, j ‐ 1)

TF(1, j) = TI(1, j) + tl(seq(1), j)

Next j

For i = 2 To N

TI(i, 1) = TF(i ‐ 1, 1)

TF(i, 1) = TI(i, 1) + tl(seq(i), 1)

Next i

For i = 2 To N

For j = 2 To M

If TF(i, j ‐ 1) > TF(i ‐ 1, j) Then

temp = TF(i, j ‐ 1)

Else

temp = TF(i ‐ 1, j)

End If

TI(i, j) = temp

TF(i, j) = TI(i, j) + tl(seq(i), j)

Next j 43

Next i

C_max = TF(N, M)

Cells(N + 4, 28) = C_max

End Sub

Palmer – Risultati

Palmer

Soluzione

10

7

9

18

20

12

13

6

3

15

5

14

11

4

16

19

17

8

2

1

C_max

993

Gupta modificato – Codice

Private Sub CommandButton5_Click()

Const N = 20, interv = 50, min_tl = 5, M = 6

Dim seq(N), f(N), tl(N, M), TI(N, M), TF(N, M), T(N)

For i = 1 To N

For j = 1 To M

tl(i, j) = Int(Rnd * interv + min_tl)

Next j

Next i

ʹGupta modificato

If Int(M / 2) > M / 2 Then

44

H = (M + 1) / 2

Else

H = M / 2

End If

For i = 1 To N

For j = 1 To H

T(i) = T(i) + tl(i, j) ‐ tl(i, M ‐ j + 1)

Next j

diff = tl(i, 1) ‐ tl(i, 2)

For j = 2 To M ‐ 1

If diff > (tl(i, j) ‐ tl(i, j + 1)) Then diff = (tl(i, j) ‐ tl(i, j + 1))

Next j

If T(i) > 0 Then f(i) = 1 / diff

If T(i) < 0 Then f(i) = ‐1 / diff

If T(i) = 0 Then f(i) = 0

seq(i) = i ʹinizializzo la sequenza iniziale

Next i

For i = 1 To N ‐ 1

For j = i + 1 To N

If f(i) > f(j) Then

temp = seq(i): seq(i) = seq(j): seq(j) = temp

temp = f(i): f(i) = f(j): f(j) = temp

End If

Next j

Cells(i + 2, 31) = seq(i)

Next i

Cells(N + 2, 31) = seq(N)

ʹCalcolo di Cmax per lo schedule trovato

TI(1, 1) = 0: TF(1, 1) = tl(seq(1), 1)

For j = 2 To M

TI(1, j) = TF(1, j ‐ 1)

TF(1, j) = TI(1, j) + tl(seq(1), j)

Next j

For i = 2 To N

TI(i, 1) = TF(i ‐ 1, 1)

TF(i, 1) = TI(i, 1) + tl(seq(i), 1)

Next i

For i = 2 To N

For j = 2 To M

If TF(i, j ‐ 1) > TF(i ‐ 1, j) Then

temp = TF(i, j ‐ 1)

Else

temp = TF(i ‐ 1, j)

End If 45

TI(i, j) = temp

TF(i, j) = TI(i, j) + tl(seq(i), j)

Next j

Next i

C_max = TF(N, M)

Cells(N + 4, 31) = C_max

End Sub

Gupta modificato – Risultati

Gupta modificato

Soluzione 15

14

11

8

2

18

4

5

19

20

9

6

3

10

1

7

13

12

16

17

C_max 938

Algoritmo di Nawaz – Codice

Private Sub CommandButton6_Click()

Const N = 20, interv = 50, min_tl = 5, M = 6

Dim seq(N), f(N), tl(N, M), TI(N, M), TF(N, M), Z_best(N), seed(N), p(N), Z(N)

For i = 1 To N

For j = 1 To M

tl(i, j) = Int(Rnd * interv + min_tl)

p(i) = p(i) + tl(i, j)

Next j

seed(i) = i

46

Next i

For i = 1 To N ‐ 1

For j = i + 1 To N

If p(i) < p(j) Then

temp = seed(i): seed(i) = seed(j): seed(j) = temp

temp = p(i): p(i) = p(j): p(j) = temp

End If

Next j

Next i

seq(1) = seed(1): seq(2) = seed(2)

TI(1, 1) = 0: TF(1, 1) = tl(seq(1), 1)

For j = 2 To M

TI(1, j) = TF(1, j ‐ 1)

TF(1, j) = TI(1, j) + tl(seq(1), j)

Next j

TI(2, 1) = TF(2 ‐ 1, 1)

TF(2, 1) = TI(2, 1) + tl(seq(2), 1)

For j = 2 To M

If TF(2, j ‐ 1) > TF(2 ‐ 1, j) Then

temp = TF(2, j ‐ 1)

Else

temp = TF(2 ‐ 1, j)

End If

TI(2, j) = temp

TF(2, j) = TI(i, j) + tl(seq(2), j)

Next j

C_max = TF(2, M)

seq(1) = seed(2): seq(2) = seed(1)

TI(1, 1) = 0: TF(1, 1) = tl(seq(1), 1)

For j = 2 To M

TI(1, j) = TF(1, j ‐ 1)

TF(1, j) = TI(1, j) + tl(seq(1), j)

Next j

TI(2, 1) = TF(2 ‐ 1, 1)

TF(2, 1) = TI(2, 1) + tl(seq(2), 1)

For j = 2 To M

If TF(2, j ‐ 1) > TF(2 ‐ 1, j) Then

temp = TF(2, j ‐ 1)

Else

temp = TF(2 ‐ 1, j)

End If

TI(2, j) = temp

TF(2, j) = TI(i, j) + tl(seq(2), j)

Next j

If TF(2, M) > C_max Then 47

seq(1) = seed(1): seq(2) = seed(2)

Else

C_max = TF(2, M)

End If

ʹRiempiamo in ordine di p, dal terzo job fino allʹN‐esimo

For C = 3 To N

C_max_temp = 10 ^ 6 ʹBig M

For k = 1 To C ʹvalutiamo le posizioni relative

Z(k) = seed(C)

If k = 1 Then

For T = 2 To C

Z(T) = seq(T ‐ 1)

Next T

End If

If k = C Then

For T = 1 To C ‐ 1

Z(T) = seq(T)

Next T

End If

If k < C Then

If k > 1 Then

For T = 1 To k ‐ 1

Z(T) = seq(T)

Next T

For T = k + 1 To C

Z(T) = seq(T ‐ 1)

Next T

End If

End If

TI(1, 1) = 0: TF(1, 1) = tl(Z(1), 1)

For j = 2 To M

TI(1, j) = TF(1, j ‐ 1)

TF(1, j) = TI(1, j) + tl(Z(1), j)

Next j

For i = 2 To C

TI(i, 1) = TF(i ‐ 1, 1)

TF(i, 1) = TI(i, 1) + tl(Z(i), 1)

Next i

For i = 2 To C

For j = 2 To M

If TF(i, j ‐ 1) > TF(i ‐ 1, j) Then

temp = TF(i, j ‐ 1)

Else

temp = TF(i ‐ 1, j)

End If

TI(i, j) = temp

TF(i, j) = TI(i, j) + tl(Z(i), j)

Next j

48

Next i

If TF(C, M) < C_max_temp Then

C_max_temp = TF(C, M)

For pos = 1 To C

Z_best(pos) = Z(pos)

Next pos

End If

Next k

For pos = 1 To C

seq(pos) = Z_best(pos)

Next pos

Next C

For i = 1 To N

Cells(i + 2, 34) = seq(i)

Next i

Cells(N + 4, 34) = C_max_temp

End Sub

Algoritmo di Nawaz – Risultati

NEH

Soluzione

18

8

15

16

9

12

1

17

14

13

2

6

7

11

19

3

4

10

5

20

C_max

762 49

In questo paragrafo esponiamo la risoluzione del problema del commesso viaggiatore con l’algoritmo euristico

noto come TABOO. I parametri dell’euristico si intuiscono leggendo il codice.

Codice

Private Sub CommandButton1_Click()

ʹinizializzazione delle variabili;

Const N = 100, tenure = 100, simulazioni = 10000

Randomize Timer

Dim dist(N, N), seq(N), cost(N ‐ 1), seq_opt(N), vicinato(((N ‐ 1) * (N / 2)), N + 1), taboo(tenure, N)

ʹgenerazione random dei valori delle distanze tra le città;

For i = 1 To N ‐ 1

For j = i + 1 To N

dist(i, j) = Int(61 * Rnd() + 30)

dist(j, i) = dist(i, j)

Next j

Next i

ʹgenerazione sequenza iniziale: cominciamo, i.e., con la sequenza naturale;

For i = 1 To N

seq(i) = i

Next i

ʹcalcolo della funzione obiettivo D per la sequenza iniziale;

D = 0

For i = 2 To N

D = D + dist(seq(i), seq(i ‐ 1))

Next i

D = D + dist(seq(N), seq(1))

4

ʹcalcolo della funzione obiettivo temporanea. La prima volta non calcolerà nulla;

D_temp = 0

For p = 2 To N

D_temp = D_temp + dist(vicinato(k, p), vicinato(k, p ‐ 1))

Next p

D_temp = D_temp + dist(vicinato(k, N), vicinato(k, 1))

If D_temp > 0 Then GoTo 5 ʹtorna dentro il ciclo;

ʹgenerazione taboo list iniziale;

For i = 1 To N

taboo(tenure, i) = seq(i)

seq_opt(i) = seq(i)

Next i

ʹciclo per riempire la taboo list, dunque esegue le prime iterazioni in numero pari alla lunghezza della lista;

For t = 2 To (tenure)

k = 0

ʹeffettuo gli scambi, ovvero genero tutto il vicinato;

For i = 1 To N ‐ 1

50

For j = i + 1 To N

k = k + 1

For v = 1 To N

vicinato(k, v) = seq(v)

Next v

temp = vicinato(k, i)

vicinato(k, i) = vicinato(k, j)

vicinato(k, j) = temp

ʹtorno a calcolare la funzione obiettivo per la data permutazione;

GoTo 4

5 vicinato(k, N + 1) = D_temp

Next j

Next i

D_temp = 100000000

ʹcerchiamo il membro del vicinato verso cui muoverci;

For v = 1 To ((N ‐ 1) * (N / 2))

If vicinato(v, N + 1) < D_temp Then

For t_row = 1 To t ‐ 1

a = 0

For t_col = 1 To N

If taboo(t_row, t_col) <> vicinato(v, t_col) Then

a = 1

End If

Next t_col

ʹse la permutazione attuale corrisponde ad una taboo, salta subito ad analizzare la prossima

permutazione;

If a = 0 Then GoTo 99

Next t_row

ʹgiunti qui la permutazione presente ha una funzione obiettivo momentaneamente migliore tra le

ʹpermutazioni e non è taboo:

ʹpertanto possiamo impostarla come sequenza iniziale e inserirla nella taboo list;

For s = 1 To N

seq(s) = vicinato(v, s)

taboo(tenure + 1 ‐ t, s) = seq(s)

Next s

D_temp = vicinato(v, N + 1)

99 End If

Next v

ʹregistro ipotetica soluzione migliore ottenuta fin ora;

If D > D_temp Then

D = D_temp

For s = 1 To N

seq_opt(s) = seq(s)

Next s

End If

Next t 51

ʹinizio del ciclo fino allʹultima simulazione: questa volta la taboo list, dopo essere stata riempita, deve scorrere;

For simul = 1 To (simulazioni ‐ tenure)

k = 0

ʹeffettuo gli scambi, ovvero genero tutto il vicinato;

For i = 1 To N ‐ 1

For j = i + 1 To N

k = k + 1

For v = 1 To N

vicinato(k, v) = seq(v)

Next v

temp = vicinato(k, i)

vicinato(k, i) = vicinato(k, j)

vicinato(k, j) = temp

ʹtorno a calcolare la funzione obiettivo per la data permutazione;

GoTo 14

16 vicinato(k, N + 1) = D_temp

Next j

Next i

ʹfacciamo scorrere in basso la taboo list;

For g = 1 To tenure ‐ 1

For m = 1 To N

taboo(tenure + 1 ‐ g, m) = taboo(tenure ‐ g, m)

Next m

Next g

D_temp = 100000000

ʹcerchiamo il membro del vicinato verso cui muoverci;

For v = 1 To ((N ‐ 1) * (N / 2))

If vicinato(v, N + 1) < D_temp Then

For t_row = 1 To t ‐ 1

a = 0

For t_col = 1 To N

If taboo(t_row, t_col) <> vicinato(v, t_col) Then

a = 1

End If

Next t_col

ʹse la permutazione attuale corrisponde ad una taboo, salta subito ad analizzare la prossima

permutazione;

If a = 0 Then GoTo 98

Next t_row

ʹgiunti qui la permutazione presente ha una funzione obiettivo momentaneamente migliore tra le

‘permutazioni e non è taboo:

ʹpertanto possiamo temporaneamente impostarla come sequenza iniziale e inserirla nella taboo list;

For s = 1 To N

seq(s) = vicinato(v, s)

taboo(1, s) = seq(s)

Next s

D_temp = vicinato(v, N + 1)

52

98 End If

Next v

ʹregistro ipotetica soluzione migliore ottenuta fin ora;

If D > D_temp Then

D = D_temp

For s = 1 To N

seq_opt(s) = seq(s)

Next s

End If

Next simul

ʹcalcolo della funzione obiettivo temporanea;

14

D_temp = 0

For p = 2 To N

D_temp = D_temp + dist(vicinato(k, p), vicinato(k, p ‐ 1))

Next p

D_temp = D_temp + dist(vicinato(k, N), vicinato(k, 1))

If simul < (simulazioni ‐ tenure + 1) Then GoTo 16 ʹtorna dentro il ciclo;

ʹStampo la sequenza ottima e il valore relativo della funzione obiettivo

Cells(1, 1) = ʺSequenzaʺ: Cells(3, 1) = ʺDistanza percorsaʺ: Cells(4, 1) = D

For i = 1 To N

Cells(2, i) = seq_opt(i)

Next i

End Sub

Risultati

Sequenza di visita Distanza

1 3313

28

91

11

12

8

9

53

87

37

66

29

71

63

64

22

36 53


PAGINE

64

PESO

3.71 MB

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

Il presente testo costituisce una sintesi completa del corso di Programmazione Operativa della Produzione, di G. Passannanti. Il corso prevede nozioni teoriche di scheduling e algoritmi di programmazione della produzione e l’applicazione di alcuni di questi in linguaggio VBA su foglio elettronico . Per scrivere quanto segue si è preso spunto da appunti presi a lezione, materiale didattico fornito dal professore e approfondimenti sul web. Riteniamo che l’implementazione su calcolatore degli algoritmi proposti in questo corso sia di importanza rilevante ai fini di una comprensione ottima (o quanto euristica!!) dei concetti di programmazione operativa. Per questo un ultimo capitolo è dedicato alle esercitazioni. La struttura del file è la seguente.
Il Capitolo 1 introduce il lettore alla programmazione operativa trattando i suoi elementi costitutivi, quali obiettivi, vincoli e misure di prestazione.
Il Capitolo 2 è interamente dedicato ai sistemi monostadio, esponendo le regole e le procedure migliori (ottimizzanti o sub-ottimizzanti) a seconda delle situazioni particolari e degli obiettivi che si vogliono perseguire.
Il Capitolo 3 definisce il modello unidirezionale Pure Flow Shop ed espone l’algoritmo ottimizzante di Johnson e le sue estensioni.
Nel Capitolo 4 troviamo diverse tematiche legate ancora al Flow Shop: il Branch&Bound, un algoritmo di ricerca intelligente ottimizzante molto diffuso in Ricerca Operativa, gli algoritmi euristici costruttivi, gli algoritmi di ricerca locale e un approfondimento relativo al paper “Minimizing the cycle time in serial manufacturing systems with multiple dual-gripper robots” (2006, G. Galante, G. Passannanti) pubblicato sull’International Journal of Production Research.
Il Capitolo 5 passa al modello multidirezionale Job Shop, esponendo due algoritmi euristici (uno con schedulazione attiva ed uno con schedulazione non delay) e le regole di carico su cui si fondano.
Il Capitolo 6 espone due famosi algoritmi euristici di ricerca non specifici, applicabili ad una moltitudine di problemi, tra cui la programmazione operativa. Il primo paragrafo è dedicato al TABOO SEARCH, il secondo al Simulated Annealing.
Il Capitolo 7, ultimo tra quelli di teoria, è interamente dedicato alla classe degli algoritmi genetici. Vedremo le caratteristiche generali di un siffatto algoritmo, un’applicazione banale ed infine le tecniche più utilizzate per risolvere problemi di programmazione operativa con un genetico.
Nel Capitolo 8 troviamo, come annunciato, esempi di implementazione degli algoritmi visti nei paragrafi precedenti. In particolare abbiamo: schedulazioni ottimizzanti per sistemi monostadio, applicazione del Johnson, euristici per Flow Shop, un TABOO per la risoluzione di un salesman travel problem, e infine una schedulazione non delay per un Job Shop. Per ogni esercizio è riportato nell’ordine il codice nell’estensione VBA di Excel ed i risultati ottenuti.

Si augura una buona lettura


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria gestionale (AGRIGENTO, PALERMO)
SSD:
Università: Palermo - Unipa
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher RiccardoScimeca di informazioni apprese con la frequenza delle lezioni di Programmazione e gestione della produzione e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Palermo - Unipa o del prof Passannanti Gianfranco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Programmazione e gestione della produzione

Ottimizzazione di un problema di knpasack modificato
Tesi
Marketing management
Appunto
Presentazione Case Study per OIS e BPM
Esercitazione
Economia applicata all'ingegneria - Appunti
Appunto