Metody rozwiÄ…zywania
Metody rozwiÄ…zywania
problemów decyzyjnych
problemów decyzyjnych
Harmonogramowanie pracy
Harmonogramowanie pracy
Zastosowanie metody przydziału
Zastosowanie metody przydziału
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
Plan prezentacji
Istota problemu przydziału pracowników do zadań
" wprowadzenie
" praktyczne aspekty problemu
Matematyczne sformułowanie problemu przydziału
" zmienna decyzyjna
" funkcja celu
" ograniczenia
" struktura problemu przydziału
Metoda przydziału
" tablica przydziału
" główne kroki metody przydziału
" uogólniony algorytm metody przydziału
Analiza przypadku
Podsumowanie
2
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
1
Wprowadzenie
Istota problemu przydziału
Rozważmy problem przydziału pracowników do obsługi kilku regionów
sprzedaży
Przypadek 1
Przypadek 1
Przypadek 1
Przypadek 2
Przypadek 2
Przypadek 2
3
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Wprowadzenie
Istota problemu przydziału
Problem przydziału pracowników do obsługi kilku regionów& cd
Przypadek 3
Przypadek 3
Przypadek 3
4
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
2
Wprowadzenie
Istota problemu przydziału
Problemy spotykane w praktyce charakteryzują się znacznie większym
stopniem skomplikowania
Liczba Liczba
Liczba Liczba
pracowników permutacji
pracowników permutacji
i regionów
i regionów
1 1
2 2
3 6
4 24
5 120
6 720
7 5.040
8 40.320
9 362.880
10 3.628.800
& &
& &
16 20.922.789.888.000
5
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Wprowadzenie
Istota problemu przydziału
Istnieje wiele możliwości przydziału pracowników do zadań
" w praktyce
 porzuca się próby racjonalnego przydziału pracowników
 decyduje się na  zgadywanie najlepszego przydziału
Człowiek jako pracownik charakteryzuje się określonymi cechami
" efektywność pracy
" umiejętności
" zdolności
" doświadczenia
" & .
Traktując pracowników jako niezróżnicowane zasoby przedsiębiorstwo traci
szansę znaczącego podniesienia produktywności
Menadżer (pracodawca) chcący dobrać ludzi do realizacji zdefiniowanych
zadań w najlepszy możliwy sposób musi
" przewidzieć zapotrzebowanie na pracę
" poszukiwać odpowiednich ludzi
" dokonywać efektywnej alokacji pracowników
6
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
3
Metoda przydziału
Istota problemu przydziału
Problem przydziału w ogólności polega na delegowaniu
pracowników do poszczególnych prac, w taki sposób, aby
pracowników
koszt realizacji wszystkich prac był minimalny
koszt
Szersze rozumienie problemu
" pracownik urzÄ…dzenie
" koszt czas, odległość, inne mierniki efektywności
Założenie dotyczące przydziału pracowników do zadań
" tylko jeden pracownik może być przydzielony do jednego zadania
" jedno zadanie ma przydzielone tylko jednego pracownika
7
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Istota problemu przydziału
Przykłady zadań jednocześnie wykonywanych przez różną liczbę
pracowników (osób)
Ludzie
1 2 3 & 11
Zadania
kierowanie autobusem miejskim &
kierowanie autobusem międzymiastowym
&
(przewóz krajowy)
kierowanie autobusem międzymiastowym
&
(przewóz międzynarodowy)
& & & & & &
rozładunek towaru &
& & & & & &
gra w piłkę nożną &
8
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
4
Metoda przydziału
Istota problemu przydziału
Jeżeli tylko jeden pracownik może zostać przydzielony do jednego zadania,
pracownik zadania
wówczas
" z punktu widzenia matematycznego zapisu problemu zmienną decyzyjną będzie
wartość
 xij = 1 jeżeli i-ty pracownik jest przedzielony do wykonywania j-tej pracy
 xij = 0 jeżeli i-ty pracownik nie jest przedzielony do wykonywania j-tej pracy
" poszukujemy rozwiÄ…zania
 całkowitoliczbowego
 binarnego (0 lub 1)
" sformułowanie i rozwiązanie problemu
 problem można sformułować w postaci zadania programowania liniowego
z ograniczeniem o binarnych charakterze zmiennych decyzyjnych
 problem można rozwiązać za pomocą znanych metod
płaszczyzn odcinających Gomory ego
ograniczeń i rozgałęzień
 istnieje specyficzna metoda rozwiązywania problemu przydziału METODA PRZYDZIAA
U
METODA PRZYDZIAA
U
9
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Istota problemu przydziału
Założenia metody
" problem przydziału można potraktować jako specyficzny przypadek problemu
transportowego
" problem przydziału można zatem rozwiązać z zastosowaniem metody transportowej
TABLICA PRZYDZIAA
U
TABLICA PRZYDZIAA
U
Magazyny odbiorców / Zadania
Dostawcy/
Podaż
Pracownicy
1 2 3 4
Efektywność
Efektywność
c11 c12 c13 c14
przydziału 1 1
przydziału
x11 x12 x13 x14
pracownika do
pracownika do
c21 c22 c23 c24
zadania
zadania
2 1
x21 x22 x23 x24
c31 c32 c33 c34
Przydział
Przydział
3 1
pracownika do x31 x32 x33 x34
pracownika do
zadania (0 lub 1) 
zadania (0 lub 1) 
c41 c42 c43 c44
4 1
ZMIENNA BINARNA
ZMIENNA BINARNA
ZMIENNA BINARNA
x41 x42 x43 x44
Popyt
1 1 1 1 4
Każde zadanie może mieć Każdy pracownik
Każde zadanie może mieć Każdy pracownikmoże
może
przedzielone jednego pracownika wykonać jedno zadanie
przedzielone jednego pracownika wykonać jedno zadanie
10
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
5
Metoda przydziału
Istota problemu przydziału
Interpretacja zmiennej decyzyjnej
" załóżmy, że pomijamy wartości cij oraz np. x23 = 1
" co to w praktyce oznacza zmienna xij?
Magazyny odbiorców Zadania
Dostawcy
Podaż
Pracownicy
1 2 3 4
c11 c12 c13 c14
1 1
x11 x12 x13 x14
c21 c22 c23 c24
2 1
x21 x22 x1 x24
23
c31 c32 c33 c34
3 1
x31 x32 x33 x34
c41 c42 c43 c44
4 1
x41 x42 x43 x44
Popyt 1 1 1 1 4
jeżeli x23 = 1 x21= x22 = x24= 0
jeżeli x23= 1 x21 = x22= x24 = 0
również x13 = x33= x43 = 0
również x13= x33 = x43= 0
11
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Model matematyczny problemu
Problem przydziału sformułowany w postaci zadania programowania
liniowego
Ogólne sformułowanie funkcji celu minimum całkowitych kosztów
realizacji wszystkich zadań (prac)
m n
Koszt = xij min
""cij
i =1 j =1
gdzie:
cij  jednostkowy koszt realizacji j-tego zadania przez i-tego pracownika,
i = 1, 2, ..., m; j = 1, 2, ..., n
m  zbiór pracowników
n  zbiór zadań (prac)
xij  zmienna decyzyjna wskazująca przydział i-tego pracownika do j-tego zadania,
xij = 0 *" 1
12
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
6
Metoda przydziału
Model matematyczny problemu
Jednostkowy koszt realizacji
j-tego zadania przez i-tego
pracownika zależy od
" predyspozycji i inteligencji
" motywacji
" kompetencji pracownika
" wieku
" wyposażenia stanowiska
(zaawansowania technolo-
Czas
gicznego urzÄ…dzenia)
KRZYWA UCZENIA SI

" częstotliwości powtarzania
" &
" doświadczenia i praktyki
pracownika
Liczba powtórzeń
13
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Model matematyczny problemu
Ograniczenia
Pracownicy Zadania
" i-ty pracownik może być
1 1
przydzielony tylko do jednego
xi1
zadania
2
2
xi2
n
xij
xij = 1; i = 1,2,...., m
"
i j
j =1
xin
n
m
Pracownicy Zadania
" do j-tego zadania może być 1 1
x1j
przydzielony tylko jeden
2
2
x2j
pracownik
m
xij
i j
xij = 1; j = 1,2,...., n
"
xmj
i =1
m
n
14
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
7
Jednostkowy czas realizacji
Skumulowana liczba zrealizowanych zada
Å„
Metoda przydziału
Model matematyczny problemu
Model matematyczny problemu przydziału klasyczny przypadek
" funkcja celu minimalizacja kosztu wykonania wszystkich zadań
m n
Koszt = xij min
""cij
i =1 j =1
" przy ograniczeniach
n
xij = 1; i = 1,2,...., m
"
j =1
m
xij = 1; j = 1,2,...., n
"
i =1
xij " 0 *"1
" przyjęte ograniczenie wymusza kwadratowy wymiar tablicy m=n
 liczba pracowników równa jest liczbie zadań do wykonania
15
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Zważywszy na postać zmiennej decyzyjnej tablica przydziału może przyjąć
postać uwzględniającą wyłącznie komórki kosztów
Zadania
Pracownicy Przydział
1 2 3 4
1 c11 c12 c13 c14 1
2 c21 c22 c23 c24 1
3 c31 c32 c33 c34 1
4 c41 c42 c43 c44 1
Przydział 1 1 1 1 4
Problem dokonaj przydziału pracowników do zadań w kategoriach czasu
realizacji zadań (minimalizacja czasu wykonania wszystkich prac)
" pracownicy: 1, 2, 3, 4
" zadania: 1, 2, 3, 4
16
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
8
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
W tablicy zamieszczono szacunkowe czasy realizacji poszczególnych zadań
przez każdego z pracowników, wyrażone w [godz.]
Zadania
Pracownicy Przydział
1 2 3 4
1 5 3 1 5 1
2 6 6 2 7 1
3 5 5 3 8 1
4 8 2 4 3 1
Przydział 1 1 1 1 4
najkrótszy czas realizacji zadania 4
najkrótszy czas realizacji zadania 4
najkrótszy czas realizacji zadania 3
najkrótszy czas realizacji zadania 3
najkrótszy czas realizacji zadania 2
najkrótszy czas realizacji zadania 2
najkrótszy czas realizacji zadania 1
najkrótszy czas realizacji zadania 1
17
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
KROK 1: od każdego  czasu realizacji w wierszu odejmij najmniejszą
wartość w tym wierszu
Zadania
Pracownicy Przydział
1 2 3 4
1 5  1 3  1 1  1 5  1 1
2 6  2 6  2 2  2 7  2 1
3 5  3  3  3  3
5 3 8 1
4 8  2 2  2 4  2 3  2 1
Przydział 1 1 1 1 4
18
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
9
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Tablica przydziału po kroku 1
Zadania
Pracownicy Przydział
1 2 3 4
1 4  2  0  0  1
2 0 4 1
2 4  2  0  0  1
4 0 5 1
3 2  2  0  0  1 1
2 0 5
4 6  2 0  0 2  0 1  1 1
Przydział 1 1 1 1 4
KROK 2: od każdego  czasu realizacji w kolumnie odejmij najmniejszą
wartość w tej kolumnie
19
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Tablica przydziału po kroku 2
Zadania
Pracownicy Przydział
1 2 3 4
1 2 2 0 3 1
2 2 4 0 4 1
3 0 2 0 4 1
4 4 0 2 0 1
Przydział 1 1 1 1 4
KROK 3: Narysuj minimalnÄ… liczbÄ™ linii przechodzÄ…cych przez wszystkie
 zera
KROK 4: Oceń ile powstało linii
" ponieważ tablica ma wymiar 4 4 minimalna liczba linii powinna wynosić 4,
wówczas przydział pojedynczych pracowników do zadań będzie optymalny
" jeżeli warunek nie jest spełniony poszukujemy innych możliwości KROK 5
20
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
10
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
KROK 5: Znajdz
najmniejszą liczbę spośród wartości, przez które nie
przechodzi żadna linia
" odejmij od każdego  czasu realizacji nie objętego linią
" dodaj do każdego  czasu realizacji objętego dwiema liniami
Zadania
Pracownicy Przydział
1 2 3 4
1 2  2  2
1
2 0 3  2
2 2  2  2 1
4 0 4  2
+2
3 0 2 0 4 1
+2
4 4 0 2 0 1
Przydział 1 1 1 1 4
21
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Tablica przydziału po kroku 5
Zadania
Pracownicy Przydział
1 2 3 4
1 0 0 0 1 1
2 0 2 0 2 1
3 0 2 2 4 1
4 4 0 4 0 1
Przydział 1 1 1 1 4
KROK 6: Ponownie narysuj minimalnÄ… liczbÄ™ linii przechodzÄ…cych przez
wszystkie  zera
KROK 7: Oceń ile powstało linii
" minimalna liczba linii wynosi 4 możliwy jest optymalny przydział pracowników do
zadań
" powstała tablica jest tablicą finalną
22
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
11
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
KROK 8: Powróć do pierwotnej tablicy przydziału i dokonaj przydziału na
podstawie komórek, które w finalnej tablicy miały wartość  zero
Zadania
Pracownicy Przydział
1 2 3 4
1 5 3 1 5 1
2 6 6 2 7 1
3 5 5 3 8 1
4 8 2 4 3 1
Przydział 1 1 1 1 4
Czas realizacji prac (efektywność realizacji wszystkich zadań wynosi:
5×(1) + 3×(1) + 2×(1) + 3×(1) = 13 godz.
23
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Algorytm metody przydziału
(0) przygotuj tablicę przydziału, zawierającą koszty przydziału (lub inny wskaz
nik
efektywności) pracowników do zadań
(1) zidentyfikuj najmniejszą wartość w każdym wierszu i odejmij ją od każdego
elementu w tym wierszu
(2) zidentyfikuj najmniejszą wartość w każdej kolumnie i odejmij ją od każdego
elementu w tej kolumnie
(3) narysuj minimalnÄ… liczbÄ™ linii przechodzÄ…cych przez wszystkie  zera
(4) oceń ile linii powstało w kroku (3)
" jeżeli liczba linii równa jest wymiarowi tablicy n, wówczas możliwy jest optymalny
przydział pracowników
" jeżeli liczba linii jest mniejsza od n przejdz
do kroku (5)
(5) znajdz
najmniejszą liczbę w tablicy, spośród wartości, przez które nie przechodzi
żadna linia
" odejmij tę wartość od tych, przez które nie przechodzi żadna linia
" dodaj tę wartość do wszystkich, przez które przechodzą 2 linie
24
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
12
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Algorytm metody przydziału & cd
(6) na tablicy powstałej w kroku (5) zrealizuj krok (3), ponownie rysując minimalną
liczbÄ™ linii Å‚Ä…czÄ…cych wszystkie  zera
(7) przejdz
do kroku (4) oceniajÄ…c liczbÄ™ linii
" jeżeli minimalna liczba linii jest równa wymiarowi tablicy przydziału,
 dokonaj przydziału pracowników do zadań na podstawie komórek, które w finalnej
tablicy przydziału mają wartości  zero
 oblicz wartość funkcji celu
" jeżeli minimalna liczba linii jest mniejsza niż wymiar tablicy przydziału wróć do kroku (5)
25
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Analiza przypadku
Dokonaj analizy problemu, zgodnie z załączonym
opisem przypadku
" przeprowadz
analizÄ™ problemu
" sformułuj model matematyczny problemu
" rozwiąż problem z zastosowaniem metody przydziału
" wykorzystaj Solver dla MS Excel
Istota problemu
" przydział motorniczych do realizacji poszczególnych
zadań
 wariant 1: przydział 13 kierowców do 13 zadań
 wariant 2: przydział 14 kierowców do 14 zadań
" jak zmieni się przydział pracowników (1-13) po
Opis
Opis
problemu
problemu
wprowadzeniu pracownika nr 14?
RozwiÄ…zanie
RozwiÄ…zanie
26
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
13
Metoda przydziału
Analiza przypadku / W1
Tworzenie arkuszy
roboczego w MS
Excel dla Wariantu 1
Tablica kosztów realizacji
Tablica kosztów realizacji
poszczególnych zadań
poszczególnych zadań
Tablica przydziału
Tablica przydziału
pracowników do zadań
pracowników do zadań
Funkcja celu (suma iloczynów)
Funkcja celu (suma iloczynów)
27
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Analiza przypadku / W1
Definiowanie
parametrów modelu
w Solverze
28
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
14
Metoda przydziału
Analiza przypadku / W1
Rozwiązanie problemu w wariancie 1 dobowy koszt realizacji zadań
(1-13) wynosi 307 jednostek
G
H B
A G I
K H E
M D J
F C L B
0:00 4:00 8:00 12:00 15:00 19:00 22:00 2:00
29
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metoda przydziału
Analiza przypadku / W2
Tworzenie arkuszy
roboczego w MS
Excel dla Wariantu 2
14-te (dodatkowe) zadanie
14-te (dodatkowe) zadanie
14-ty (dodatkowy) pracownik
14-ty (dodatkowy) pracownik
30
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
15
Metoda przydziału
Analiza przypadku / W2
Rozwiązanie problemu w wariancie 2 dobowy koszt realizacji zadań
(1-14) wynosi 329 jednostek
" wykonanie zadań (1-13)
329  20 = 309
Nowy pracownik
G B
N
H F
A G I
K H E
M D J
C N L B
0:00 4:00 8:00 12:00 15:00 19:00 22:00 2:00
31
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Podsumowanie
Podstawowe pojęcia
" matematyczne sformułowanie
problemu przydziału
" zmienna binarna i jej interpretacja
" tablica przydziału
" istota klasycznej metody przydziału
" algorytm metody przydziału
" metoda przydziału a metoda
transportowa
32
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
16
Podsumowanie
Zalety zastosowania metody
przydziału
" proste sformułowanie matematyczne
" jeden pracownik do jednego zadania
choć możliwe jest zastosowanie zadań
przewidzianych do realizacji
równocześnie przez dwie osoby
" metoda rozwiÄ…zywalna za pomocÄ…
klasycznego narzędzia MS Excel
(max 200 zmiennych decyzyjnych)
33
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
33
Metody rozwiÄ…zywania
Metody rozwiÄ…zywania
problemów decyzyjnych
problemów decyzyjnych
Harmonogramowanie pracy
Harmonogramowanie pracy
Zastosowanie metody przydziału
Zastosowanie metody przydziału
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
pok. 719, tel. [phone]
E-mail: [e-mail]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
URL: http://www.put.poznan.pl/~piotrs
17