Kopia Met przydz

background image

1

Zarządzanie transportem

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
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

background image

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

background image

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

background image

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

background image

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

background image

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Ę

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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)

background image

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)

background image

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

background image

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

background image

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


Wyszukiwarka

Podobne podstrony:

więcej podobnych podstron