Harmonogramowanie produkcji

Polega na:



rozłożeniu w czasie przydziału zasobów do zleceń

produkcyjnych,



podziale zleceń na partie produkcyjne,



określeniu terminów rozpoczęcia i zakończenia

realizacji partii produkcyjnych na poszczególnych

maszynach.

Harmonogramowanie produkcji jest ściśle związane z

planowaniem produkcji.

Kryteria optymalności harmonogramu produkcji reprezentują

kompromis pomiędzy kosztami niedotrzymania terminów

zaspokojenia zapotrzebowania, kosztami utrzymywania zapasów

i kosztami częstych zmian asortymentu produkcji.

Klasyczną metodą

harmonogramowania produkcji jest

szeregowanie zadań

Rozwiązaniem problemu szeregowania zadań jest

uszeregowanie, zwane też harmonogramem

Elementarne

pojęcia:

•zadania,

•zasoby.

Zadania

(zlecenia) – wykonanie ciągu

czynności zwanych operacjami, z których

każdy wymaga zaangażowania

określonych

zasobów

.

Przykłady

zadań:

proces obróbki detalu - w przemyśle maszynowym,

proces montażu – w przemyśle samochodowym,

realizacja inwestycji – w budownictwie,

przygotowanie promu kosmicznego do wystrzelenia – w

realizacji projektu naukowo-badawczego,

przetworzenie partii surowca – w przemyśle

petrochemicznym.

Termin gotowości, żądany termin zakończenia, przerywalność,

podzielność, sposoby wykonywania operacji (szczególne

żądania zasobowe, alternatywne sposoby wykonania)

Elementarne

pojęcia:

•zadania,

•zasoby.

Przykłady

zasobów:

• odnawialne (procesor, maszyny, robot) – ograniczenia

strumienia dostępności,

• nieodnawialne (surowce energetyczne, materiały

podlegające zużyciu) – ograniczenie globalnej ilości,

• podwójnie ograniczone (energia, kapitał)

Dostępność (czasowe przedziały dostępności), ilość, koszt,

podzielność (w sposób ciągły lub dyskretny), przywłaszczalność

6

Wybrane kryteria oceny harmonogramu



długość uszeregowania



średni czas przepływu



maksymalne opóźnienie



średnie spóźnienie

n

n

C

C

max

max



)

(

|

|

1

|

|

1

_

n

N

n

n

o

N

n

n

o

r

C

N

F

N

F

o

o















)

(

max

max

max

n

n

n

n

n

d

C

L

L







}

0

,

max{

|

|

1

|

|

1

_

n

N

n

n

o

N

n

n

o

d

C

N

T

N

T

o

o















7

Szeregowanie zadań

W systemie składającym się z

M

stanowisk roboczych (maszyn) należy

wykonać

N

zleceń. Każde zlecenie jest poleceniem wykonania

określonej liczby sztuk produktu o numerze

j = j

n

Proces wytwarzania produktu

j

składa się z operacji o numerach

k



K

j

Zadanie jest poleceniem jednokrotnego bądź wielokrotnego wykonania

danej operacji.

Operacje należące do procesu wytwarzania dowolnego produktu muszą

być wykonywane w określonej kolejności

Zadania są wykonywane na stanowiskach roboczych:



równoległych (spełniających te same funkcje),



dedykowanych (różniących się wykonywanymi funkcjami)

8

Szeregowanie zadań

Dla maszyn dedykowanych wyróżnia się trzy systemy obsługi:

1.

Otwarty (

open shop

) - każde zadanie musi być wykonywane przez

wszystkie maszyny ale kolejność wykonywania nie jest narzucona,

2.

Przepływowy (

flow shop

) - każde zadanie musi być wykonywane w

tej samej kolejności przez wszystkie maszyny

3.

Ogólny (

job shop

) – podzbiór maszyn mających wykonać dane

zadanie oraz kolejność wykonywania każdego zadania są dowolne, choć

określone.

9

Szeregowanie zadań dla zleceń jednostkowych

o ustalonych marszrutach (

problem job shop

)

Założenia:

1.

Zlecenia są jednostkowe i dotyczą różnych produktów.

Dlatego mogą być numerowane indeksem produktów j.

2.

Zadania

są

jednostkowe,

niepodzielne

i

będą

identyfikowane, jak operacje, parami indeksów (j,k).

3.

Kolejność operacji-zgodna z numeracją (liniowy porządek).

4.

Marszruty są ustalone (maszyny dedykowane), więc dany

jest przydział stanowisk do operacji i(j,k). Dlatego

problem szeregowania zadań sprowadza się do

wyznaczenia chwil rozpoczęcia zadań S

nk

, przy czym

czasy wykonania zadań (operacji) t

jk

mogą być określone

bez podania indeksu stanowiska.

Reguły dyspozytorskie przydziału priorytetów do zadań

oczekujących przed maszynami na wykonanie:



LPT

(

longest processing time),

najdłuższy czas wykonania



SPT

(

shortest processing time),

najkrótszy czas wykonania



FIFO

(

first in – first out

), pierwszy przybył – pierwszy

obsłużony



LIFO

(

last in – first out

), ostatni przybył – pierwszy

obsłużony



EDD

(

earliest due time

), kolejność wykonania zadań

według terminów zamknięcia zleceń, czyli ich zadanych

czasów zakończenia



LWR

(

least work remaining

), kolejność wykonania zadań

według rosnących sum czasów przetwarzania zadań

pozostałych do wykonania w zleceniach

W systemie składającym się z czterech maszyn:

Przykład

należy wykonać cztery zlecenia o następujących czasach przybycia, marszrutach i czasach
przetwarzania zadań:

1

2

3

4

0

0

20

30

Zlecenia

j

Czas przybycia

r

j

Sekwencja zadań
(czas wykonania)

L(10) – D(20) – G(35)

D(25) – L(20) – G(30) – M(15)

D(10) – M(10)

L(15) – G(10) – M(20)

Rozwiązanie problemu otrzymuje się analizując kolejne

chwile, które mogą być chwilami startu pewnych zadań.
Zadanie może być rozpoczęte w chwili:



otwarcia zlecenia (jeśli zadanie jest pierwsze w zleceniu i

wolna jest maszyna, na której zadanie to ma być wykonane),



zakończenia poprzedniego zadania w zleceniu (jeśli wolna

jest maszyna, na której ma być wykonane zadanie),



zwolnienia maszyny, na której zadanie ma być wykonane.

Może się zdarzyć, że na zwolnienie maszyny oczekuje więcej

niż jedno zadanie. Wówczas powstaje konflikt, a do jego

rozstrzygnięcia stosuje się przyjętą regułę priorytetu.

LWR

15

Szeregowanie zadań na pojedynczej maszynie

Założenia:

1.

zlecenia są jednostkowe i dotyczą różnych produktów.

Dlatego mogą być numerowane indeksem produktów j,

2.

zlecenia są tożsame z zadaniami,

3.

brak ograniczeń kolejnościowych.

Należy zdecydować o kolejności wykonywania zadań

na maszynie

n

C

16

Szeregowanie zadań na pojedynczej maszynie



Średni czas przepływu i średnie opóźnienie są minimalne

dla uszeregowania SPT



Maksymalne opóźnienie

L

max

i maksymalne spóźnienie

T

max

są

minimalne dla uszeregowania EDD



Średnie spóźnienie (suma spóźnień) jest minimalne dla

metody podziału i oszacowań

L

T

F

17

Szeregowanie zadań na maszynach

równoległych

Założenia:

1.

zlecenia są jednostkowe i dotyczą różnych produktów.

Dlatego mogą być numerowane indeksem produktów j,

2.

zlecenia są tożsame z zadaniami,

3.

brak ograniczeń kolejnościowych.

Należy zdecydować o przydziale zadań do maszyn i

o kolejności wykonywania przydzielonych zadań na

każdej maszynie

18

Szeregowanie zadań na maszynach

równoległych



Algorytm Mc Naughtona dla zadań wywłaszczalnych



Szeregowanie zadań niepodzielnych za pomocą

algorytmów listowych



Algorytm SPT (kryterium oceny uszeregowania: średni czas

przepływu)



Algorytm LPT (kryterium oceny uszeregowania: długość

uszeregowania)



Algorytm RPT (kryterium oceny uszeregowania: długość

uszeregowania i średni czas przepływu)

19

Szeregowanie zadań wywłaszczalnych

Zadania wywłaszczalne - takie zadania, których

wykonywanie na danej maszynie może zostać przerwane w

pewnej chwili czasu, a później (lub nawet w tej samej chwili

czasu) wznowione na tej samej lub innej maszynie.

Aby uszeregować zadania wywłaszczalne można zastosować

algorytm McNaughtona.

Algorytm Mc Naughtona

Mając

n

zadań i

m

maszyn, na których zadania te mają zostać

wykonane, można wyznaczyć długość uszeregowania :







n

1

j

j

j

j

*

max

}

τ

m

1

},

τ

{

max

{

max

C

1.

Rozpocznij

wykonywanie

dowolnego

zadania

na

dowolnym procesorze w chwili

t

= 0

2.

Wybierz dowolne nie uszeregowane zadanie i rozpocznij

jego wykonywanie na tym samym procesorze. Powtarzaj

krok 2, aż do osiągnięcia lub wyczerpania zbioru zadań.

3.

Część zadania pozostającą po osiągnięciu
przydziel do innego wolnego procesora zaczynając od

t

= 0. Wróć do kroku 2.

*

max

C

Przykłady:

Z

1

Z

2

Z

2

Z

3

Z

4

Z

4

Z

5

P

3

P

1

P

2











5

1

j

j

4

3

1

j

j





12

2

3

2

3

2















j



1

2

3

4

5

2

3

2

3

2

j

Z

1

Z

3

Z

2

Z

3

Z

4

Z

4

Z

5

P

3

P

1

P

2









5

1

3

3

1

4

j

j





10

1

2

4

2

1















j



1

2

3

4

5

1

2

4

2

1



j







n

1

j

j

j

j

*

max

}

τ

m

1

},

τ

{

max

{

max

C

4

3,12/3)

(

max

C

*

max





4

4,10/3)

(

max

C

*

max





23

Szeregowanie zadań dla procesów

przepływowych



kierunek przepływu wszystkich zleceń jest ten sam



liczba zadań i użyte maszyny zależą od zlecenia

Ogólny przepływowy system obsługi.

25

Szeregowanie zadań dla procesów

przepływowych



kierunek przepływu wszystkich zleceń jest ten sam



liczba zadań jest równa liczbie maszyn

Idealny przepływowy system obsługi.

26

Szeregowanie zadań dla procesów

przepływowych

Algorytm Johnsona dla systemu przepływowego z dwiema
maszynami (algorytm ten minimalizuje długość uszeregowania
C

max

zadań niepodzielnych )

Krok 1.

Wybierz zlecenia dla których

2j

j

1

τ

τ



Przydzielaj zadania tych zleceń do maszyn w kolejności nie
malejących



1j

.

Krok 2.

Pozostałe zlecenia uporządkuj w kolejności nie

rosnących



2j

zachowując tę samą kolejność zleceń na

każdej z dwu maszyn.

28

Szeregowanie zadań dla procesów

przepływowych

Przykład:

Krok 1.

5,1,4, 3,2

Krok 2.

25

C

*

max



29

Balansowanie linii montażowej (BLM)

Idea balansowania linii montażowej polega na wyznaczeniu
minimalnej liczby stanowisk pracy (stacji, maszyn) poprzez
optymalne

ale

uwzględniające

ograniczenia

kolejnościowe,

rozdzielenie operacji na stanowiska.

1

2

5

4

3

M1

M2

M3

niewykorzystany czas pracy maszyn tworzących linię montażową

30

Balansowanie linii montażowej

Stacja robocza

jest to segment linii montażowej, na której

wykonywane są określone operacje. Jest ona scharakteryzowana
przez

swoją wielkość, wyposażenie oraz rodzaj operacji

możliwych do wykonania.
Stacje robocze mogą być podzielone ze względu na operatora na:



stacje obsługi ręcznej,



zautomatyzowane



zrobotyzowane.

Zbiór

wykonywanych na stacji roboczej

operacji

nazwano jej

obciążeniem

Ruch na linii montażowej odbywa się od stacji początkowej do stacji
końcowej, bez możliwości pominięcia jakiejkolwiek stacji pośredniej.

31

Montaż

jest to proces gromadzenia i dopasowania do siebie

różnych części w celu stworzenia finalnego produktu. Opisany jest
przez wykaz części oraz czynności niezbędnych do wykonania
zadania.

Operacja

jest to elementarna czynność całkowitego procesu

montażu wykonywana na linii technologicznej. Czas konieczny do
realizacji operacji nazwany został czasem wykonania operacji.
Operacja jest rozważana jako czynność niepodzielna, gdyż żadna
z operacji nie może być podzielona ma mniejszą czynność.

Balansowanie linii montażowej

32

Balansowanie linii montażowej

Cykl

- wielkość, która charakteryzuje maksymalny czas obsługi

montowanego produktu na każdej ze stacji roboczej.

Jest parametrem wyznaczanym w oparciu o planowaną wielkość
produkcji.

Jednostka cyklu związana jest z jednostką czasów wykonywania
operacji.

33

Definicja problemu BLM

Założenie 1

Wszystkie parametry wejściowe są znane

Założenie 2

Operacja nie może być przydzielona pomiędzy dwie lub

więcej stacji roboczych

Założenie 3

Operacje muszą być wykonane zgodnie z wymaganiami

technologicznymi przedstawionymi w postaci relacji kolejnościowych

34

Definicja problemu BLM

Założenie 4

Wszystkie operacje muszą być wykonane

Założenie 5

Każda ze stacji jest wyposażona w narzędzia umożliwiające

wykonanie każdej z operacji (koszty każdej stacji są stałe)
Założenie 6

Czas

wykonania

operacji

jest

stały niezależnie od

przydzielenia do stacji roboczej

35

Definicja problemu BLM

Założenie 7

Każda operacja może być wykonana na dowolnej stacji

Założenie 8

Linia

nie

posiada

żadnych

struktur

równoległych

i jest rozważana jako szeregowa
Założenie 9

Projektowana

linia

jest

przeznaczona

do

produkcji

pojedynczego modelu produktu

36

Definicja problemu BLM

Typ1

- cykl jest stały i dany.

Celem jest minimalizacja przestojów stacji co jest równoważne z
minimalizacją liczby stanowisk pracy.

Typ 2

- liczba stacji jest dana i jest stała.

Celem jest minimalizacja cyklu balansowanej linii co jest
równoważne z maksymalizacją produkcji.

37

Klasyczny model BLM uwzględnia jedynie: zbiór operacji
z relacją kolejnościową oraz czasy operacji (przy zadanym
cyklu).

Matematyczny opis problemu BLM

Dany jest

zbiór operacji montażowych

:

 

 





i

i

n

,

, ,...,

12

38

Matematyczny opis problemu BLM

Wszystkie operacje na linii montażowej wykonywane są
według kolejności opartej o

macierz relacji kolejności

wykonywania operacji



:

v,i = 1,2,.....,n







v i

v

,

















1

0

operacja

jest bezpośrednim

poprzednikiem operacji

w przeciwnym przypadku

i

39

Matematyczny opis problemu BLM

Czasy wykonywania operacji

:

 

n

i

i

,...,

2

,

1

,









Dany jest także

cykl linii montażowej

, który spełnia

warunek:













n

i

i

i

n

i

c

1

1

max





40

Matematyczny opis problemu BLM

Problem BLM w takim modelu polega na

wyznaczeniu

stacji dla wykonywania danego podzbioru operacji, tak
aby

optymalny

balans

linii

montażowej spełniał

kryterium

minimalizacji

niewykorzystanego

czasu

pracy

:

M

,...,

2

,

1

m

min,

m

i

c

Q

M

m

1

m

i







































Q Mc

i

i

m













 

min

lub

41

Algorytmy BLM



dokładne

(metoda

liniowego

programowania

dyskretnego,

programowania

sieciowego,

programowania

dynamicznego, podziału i oszacowań)



heurystyczne

42

Algorytmy BLM

Heurystyczne (m.in.):



Ranked Positional Weight – wagowe określenie

pozycji każdej operacji (czas najdłuższej ścieżki od
początku operacji do końca sieci)



Kilbridge’a i Wester’a- ustala się porządek operacji

oparty o liczbę operacji, które rozważaną operację
poprzedzają



Metoda macierzy kolejnościowej Hoffmana

43

Miary metody BLM

Najlepsze balansowanie linii montażowych oznacza

takie połączenie operacji, by dla każdej stacji roboczej

suma czasów elementarnych była równa czasowi cyklu.

Miary

które

pozwalają

na

porównywanie

metod

używanych do BLM:

1.

efektywność linii – Line Efficiency (LE),

2.

współczynnik gładkości – Smoothness Index (SI),

3.

czas linii - Time (T).

44

Miary metody BLM

Efektywność linii (LE)

gdzie:

K – ilość stacji roboczych,

c – czas cyklu,

ST – czas wykorzystania stacji

%

100

1











K

c

ST

LE

K

i

i

45

Miary metody BLM

Współczynnik gładkości (SI)

gdzie:

ST

max

– maksymalny czas stacji roboczej,

ST

i

– czas stacji i.









K

i

i

ST

ST

SI

1

2

max

)

(

46

Miary metody BLM

Czas linii (T)

gdzie:

K – ilość stacji roboczych,

c – czas cyklu,

ST

K

– czas ostatniej stacji.

K

ST

c

K

T









)

1

(