1

Zarządzanie transportem

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs

Metoda przydziału

Piotr Sawicki / Zarządzanie transportem

2

Plan prezentacji

Istota problemu przydziału pracowników do zadań

•

istota problemu

•

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 rzeczywistego problemu przydziału

2

Piotr Sawicki / Zarządzanie transportem

3

Wprowadzenie

Istota problemu przydziału

Rozważmy problem przydziału pracowników do obsługi poszczególnych
regionów

Przypadek 1

Przypadek 1

Przypadek 1

Przypadek 2

Przypadek

Przypadek

2

2

Piotr Sawicki / Zarządzanie transportem

4

Wprowadzenie

Istota problemu przydziału

Problemy spotykane w praktyce charakteryzują się znacznie większym
stopniem skomplikowania

20.922.789.888.000

16

…

…

…

…

3.628.800

10

362.880

9

40.320

8

5.040

7

720

6

120

5

24

4

6

3

2

2

1

1

Liczba

Liczba

permutacji

permutacji

Liczba

Liczba

pracowników

pracowników

i regionów

i regionów

3

Piotr Sawicki / Zarządzanie transportem

5

Wprowadzenie

Istota problemu przydziału

Z uwagi na wiele możliwości przydziału większość przedsiębiorstw

•

porzuca próby racjonalnego przydziału pracowników

•

decyduje się na „zgadywanie” najlepszego przydziału

Człowiek jako pracownik charakteryzuje się określonymi cechami

•

efektywnością pracy

•

umiejętnościami

•

zdolnościami

•

doświadczeniem

•

….

W tej sytuacji traktując pracowników jako niezróżnocowane zasoby

przedsiębiorstwo traci szansę znaczącego podniesienia produktywności

Menadżer (pracodawca) chcący dobrać najlepszych ludzi do najlepszej

realizacji zdefiniowanych zadań musi

•

przewidzieć zapotrzebowanie na pracę

•

poszukiwać odpowiednich ludzi

•

dokonywać efektywnej alokacji pracowników

Piotr Sawicki / Zarządzanie transportem

6

Metoda przydziału

Istota problemu przydziału

Problem przydziału w ogólności polega na delegowaniu

pracowników

pracowników

do poszczególnych prac, w taki sposób, aby

koszt

koszt

realizacji wszystkich prac był minimalny

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

4

Piotr Sawicki / Zarządzanie transportem

7

Metoda przydziału

Istota problemu przydziału

Podział zadań ze względu na liczbę jednocześnie wykonujących
pracowników (osób)

…

¯

kierowanie pociągiem pasażerskim IC

…

…

…

…

…

…

…

¯

gra w piłkę nożną

…

…

…

…

…

¯

¯

¯

¯

rozładunek wagonu

…

…

…

…

…

¯

kierowanie pociągiem towarowym

¯

kierowanie tramwajem

11

3

2

1

Ludzie

Zadania

Piotr Sawicki / Zarządzanie transportem

8

Metoda przydziału

Istota problemu przydziału

Jeżeli tylko jeden

pracownik

pracownik

może zostać przydzielony do jednego

zadania

zadania

,

wówczas

•

z punktu widzenia matematycznego zapisu problemu zmienną decyzyjną będzie
wartość

– x

ij

= 0 jeżeli i-ty pracownik nie jest przedzielony do wykonywania j-tej pracy

– x

ij

= 1 jeżeli i-ty pracownik 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 PRZYDZIA

METODA PRZYDZIA

Ł

Ł

U

U

5

Piotr Sawicki / Zarządzanie transportem

9

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

c

44

c

43

c

42

c

41

1

4

x

44

x

43

x

42

x

41

4

1

1

1

1

Popyt

x

34

x

33

x

32

x

31

1

c

34

c

33

c

32

c

31

3

x

24

x

23

x

22

x

21

1

c

24

c

23

c

22

c

21

2

x

14

x

13

x

12

x

11

1

c

14

c

13

c

12

c

11

1

4

3

2

1

Podaż

Magazyny odbiorców

Æ

Zadania

Dostawcy

Pracownicy

Każdy pracownik może

wykonać jedno zadanie

Każdy

pracownik

może

wykonać jedno zadanie

Każde zadanie może mieć

przedzielone jednego pracownika

Każde zadanie może mieć

przedzielone jednego pracownika

Przydział

pracownika do

zadania (0 lub 1) –

ZMIENNA BINARNA

Przydział

pracownika do

zadania (0 lub 1) –

ZMIENNA BINARNA

ZMIENNA BINARNA

Efektywność

przydziału

pracownika do

zadania

Efektywność

przydziału

pracownika do

zadania

TABLICA PRZYDZIAŁU

TABLICA PRZYDZIAŁU

Piotr Sawicki / Zarządzanie transportem

10

Metoda przydziału

Istota problemu przydziału

Interpretacja zmiennej decyzyjnej

•

załóżmy, że pomijamy wartości c

ij

oraz np. x

23

= 1

•

co to w praktyce oznacza zmienna x

ij

?

c

44

c

43

c

42

c

41

1

4

x

44

x

43

x

42

x

41

4

1

1

1

1

Popyt

x

34

x

33

x

32

x

31

1

c

34

c

33

c

32

c

31

3

x

24

x

23

x

22

x

21

1

c

24

c

23

c

22

c

21

2

x

14

x

13

x

12

x

11

1

c

14

c

13

c

12

c

11

1

4

3

2

1

Podaż

Magazyny odbiorców

Æ

Zadania

Dostawcy

Pracownicy

1

jeżeli x

23

= 1 Æ x

21

= x

22

= x

24

= 0

jeżeli x

23

= 1 Æ x

21

= x

22

= x

24

= 0

również x

13

= x

33

= x

43

= 0

również x

13

= x

33

= x

43

= 0

6

Piotr Sawicki / Zarządzanie transportem

11

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)

gdzie:
c

ij

– 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)
x

ij

– zmienna decyzyjna wskazująca przydział i-tego pracownika do j-tego zadania,

x

ij

= 0

∪ 1

min

Koszt

→

=

∑∑

=

=

m

i

n

j

ij

ij

x

c

1

1

Piotr Sawicki / Zarządzanie transportem

12

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-
gicznego urządzenia)

•

częstotliwości powtarzania

•

…

•

doświadczenia i praktyki
pracownika

Skumulowana liczba zrealizowanych zada

ń

Czas Æ

Liczba powtórzeń Æ

Jednost

kowy czas realizacji

KRZYWA UCZENIA SIĘ

7

Piotr Sawicki / Zarządzanie transportem

13

Metoda przydziału

Model matematyczny problemu

Ograniczenia

•

i-ty pracownik może być
przydzielony tylko do jednego
zadania

•

do j-tego zadania może być
przydzielony tylko jeden
pracownik

m

1,2,....,

i

;

=

=

∑

=

1

1

n

j

ij

x

n

1,2,....,

j

;

=

=

∑

=

1

1

m

i

ij

x

1

2

i

m

1

2

j

n

x

i1

x

i2

x

ij

x

in

1

2

i

m

1

2

j

n

x

1j

x

2j

x

ij

x

mj

Pracownicy

Zadania

Pracownicy

Zadania

Piotr Sawicki / Zarządzanie transportem

14

Metoda przydziału

Model matematyczny problemu

Model matematyczny problemu przydziału Æ klasyczny przypadek

•

funkcja celu Æ minimalizacja kosztu wykonania wszystkich zadań

•

przy ograniczeniach

•

przyjęte ograniczenie wymusza kwadratowy wymiar tablicy m=n

– liczba pracowników równa jest liczbie zadań do wykonania

min

Koszt

→

=

∑∑

=

=

m

i

n

j

ij

ij

x

c

1

1

m

1,2,....,

i

;

=

=

∑

=

1

1

n

j

ij

x

n

1,2,....,

j

;

=

=

∑

=

1

1

m

i

ij

x

1

0

∪

∈

ij

x

8

Piotr Sawicki / Zarządzanie transportem

15

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

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

c

44

c

43

c

42

c

41

1

4

4

1

1

1

1

Przydział

1

c

34

c

33

c

32

c

31

3

1

c

24

c

23

c

22

c

21

2

1

c

14

c

13

c

12

c

11

1

4

3

2

1

Przydział

Zadania

Pracownicy

Piotr Sawicki / Zarządzanie transportem

16

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.]

3

4

2

8

1

4

4

1

1

1

1

Przydział

1

8

3

5

5

3

1

7

2

6

6

2

1

5

1

3

5

1

4

3

2

1

Przydział

Zadania

Pracownicy

najszybszy czas realizacji zadania 1

najszybszy czas realizacji zadania 1

najszybszy czas realizacji zadania 2

najszybszy czas realizacji zadania 2

najszybszy czas realizacji zadania 3

najszybszy czas realizacji zadania 3

najszybszy czas realizacji zadania 4

najszybszy czas realizacji zadania 4

9

Piotr Sawicki / Zarządzanie transportem

17

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

3

4

2

8

1

4

4

1

1

1

1

Przydział

1

8

3

5

5

3

1

7

2

6

6

2

1

5

1

3

5

1

4

3

2

1

Przydział

Zadania

Pracownicy

–1

–1

–1

–1

–2

–2

–2

–2

–3

–3

–3

–3

–2

–2

–2

–2

Piotr Sawicki / Zarządzanie transportem

18

Metoda przydziału

Rozwiązanie problemu przydziału pracowników do zadań

Tablica przydziału po kroku 1

KROK 2: od każdego „czasu realizacji” w kolumnie odejmij najmniejszą
wartość w tej kolumnie

1

2

0

6

1

4

4

1

1

1

1

Przydział

1

5

0

2

2

3

1

5

0

4

4

2

1

4

0

2

4

1

4

3

2

1

Przydział

Zadania

Pracownicy

–2

–2

–2

–2

–0

–0

–0

–0

–0

–0

–0

–0

–1

–1

–1

–1

10

Piotr Sawicki / Zarządzanie transportem

19

Metoda przydziału

Rozwiązanie problemu przydziału pracowników do zadań

Tablica przydziału po kroku 2

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

0

2

0

4

1

4

4

1

1

1

1

Przydział

1

4

0

2

0

3

1

4

0

4

2

2

1

3

0

2

2

1

4

3

2

1

Przydział

Zadania

Pracownicy

Piotr Sawicki / Zarządzanie transportem

20

Metoda przydziału

Rozwiązanie problemu przydziału pracowników do zadań

KROK 5: najmniejszą wartość w całej tablicy

•

odejmij od każdego „czasu realizacji” nie objętego linią

•

dodaj do każdego „czasu realizacji” objętego dwiema liniami

0

2

0

4

1

4

4

1

1

1

1

Przydział

1

4

0

2

0

3

1

4

0

4

2

2

1

3

0

2

2

1

4

3

2

1

Przydział

Zadania

Pracownicy

–2

–2

–2

–2

–2

–2

+2

+2

11

Piotr Sawicki / Zarządzanie transportem

21

Metoda przydziału

Rozwiązanie problemu przydziału pracowników do zadań

Tablica przydziału po kroku 5

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ą

0

4

0

4

1

4

4

1

1

1

1

Przydział

1

4

2

2

0

3

1

2

0

2

0

2

1

1

0

0

0

1

4

3

2

1

Przydział

Zadania

Pracownicy

Piotr Sawicki / Zarządzanie transportem

22

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”

Czas realizacji prac (efektywność realizacji wszystkich zadań wynosi:
5

×(1) + 3×(1) + 2×(1) + 3×(1) = 13 godz.

3

4

2

8

1

4

4

1

1

1

1

Przydział

1

8

3

5

5

3

1

7

2

6

6

2

1

5

1

3

5

1

4

3

2

1

Przydział

Zadania

Pracownicy

12

Piotr Sawicki / Zarządzanie transportem

23

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 wskaź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 przejdź do kroku (5)

(5)

znajdź 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

Piotr Sawicki / Zarządzanie transportem

24

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)

przejdź 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)

13

Piotr Sawicki / Zarządzanie transportem

25

Metoda przydziału

Analiza przypadku

Dokonaj analizy problemu, zgodnie z załączonym opisem
problemu

•

przeprowadź analizę problemu

•

sformułuj problem

•

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 motorniczych do 13 zadań
– wariant 2: przydział 14 motorniczych do 14 zadań

•

jak zmieni się przydział pracowników (1-13) po wprowadzeniu
pracownika nr 14?

Przykład

Przykład

Piotr Sawicki / Zarządzanie transportem

26

Metoda przydziału

Analiza przypadku / W1

Tworzenie arkuszy
roboczego w MS
Excel dla Wariantu 1

Tablica kosztów realizacji

poszczególnych zadań

Tablica kosztów realizacji

poszczególnych zadań

Tablica przydziału

pracowników do zadań

Tablica przydziału

pracowników do zadań

Funkcja celu (suma iloczynów)

Funkcja celu (suma iloczynów)

14

Piotr Sawicki / Zarządzanie transportem

27

Metoda przydziału

Analiza przypadku / W1

Definiowanie
parametrów modelu
w Solverze

Piotr Sawicki / Zarządzanie transportem

28

Metoda przydziału

Analiza przypadku / W1

Rozwiązanie problemu w wariancie 1 Æ dobowy koszt realizacji zadań
(1-13) wynosi 307 jednostek

F

0:00 4:00 8:00 12:00 15:00

19:00 22:00 2:00

M

C

D

K

A

H

H

G

G

L

J

E

I

B

B

15

Piotr Sawicki / Zarządzanie transportem

29

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

Piotr Sawicki / Zarządzanie transportem

30

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

C

0:00 4:00 8:00 12:00 15:00

19:00 22:00 2:00

M

N

D

K

A

H

H

G

G

L

J

E

I

B

B

N

Nowy pracownik

F

16

Piotr Sawicki / Zarządzanie transportem

31

Podsumowanie

Podstawowe pojęcia

•

matematyczne sformułowanie
problemu przydziału

•

zmienna binarna i jej interpretacja

•

tablica przydziału

•

istota metody przydziału

•

algorytm metody przydziału