Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
Jerzy Skrzypek
Kompleksowe, wielowariantowe zadanie z zakresu przydziału zadań
produkcyjnych.
Spis treści:
1.Opis problemu ........................................................................................................... 2
2.Wariant A .................................................................................................................. 2
3.Wariant B .................................................................................................................. 4
4.Wariant C .................................................................................................................. 5
5.Wariant D .................................................................................................................. 7
6.Wariant E .................................................................................................................. 8
7.Wariant F ................................................................................................................ 10
8.Wariant G ................................................................................................................ 11
Jerzy Skrzypek - Kraków 2003
1
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
1. Opis problemu
Szef firmy komputerowej ma do dyspozycji trzech pracowników, których ma zamiar
zatrudnić przy montowaniu zestawów komputerowych: „Biurowego”, „Do gier”, oraz
„Stacji graficznej”. Przydział pracowników do zadań menedżer poprzedził jednak
sprawdzeniem ilości komputerów, jakie mogą oni zmontować w ciągu dnia pracy.
Niezbędne dane zawiera tabela 1 (czyli liczbę zestawów, jaką każdy z pracowników
może zmontować w trakcie dnia pracy).
Tabela 1. Ilość zestawów zmontowanych przez pracowników w ciągu dnia pracy
Pracownik/Zestaw Biurowy Do gier Stacja graficzna
PI 7 5 6
PII 8 4 9
PIII 5 6 4
2. Wariant A
Modyfikacja założeń wyjściowych
Należy dokonać przydziału zadań poszczególnym pracownikom, przy założeniu, że
dany pracownik może montować tylko jeden zestaw, a każdy z zestawów może być
montowany tylko przez jednego pracownika. Liczba zestawów komputerowych
zmontowanych w ciągu dnia pracy powinna być jak największa.
Zmienna decyzyjna
x(i,j) oznacza przydział i-tego pracownika do montażu zestawu j-tego typu (zmienna
decyzyjna przyjmuje wartości 0 lub 1)..
Model matematyczny:
a)każdy z pracowników może montować tylko jeden zestaw:
x11+x12+x13=1
x21+x22+x23=1
x31+x32+x33=1
b)każdy z zestawów może być montowany tylko przez jednego pracownika
x11+x21+x31=1
x12+x22+x32=1
Jerzy Skrzypek - Kraków 2003
2
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
x13+x23+x33=1
Funkcja kryterium: maksymalizacja liczby zmontowanych zestawów w ciągu dnia
pracy:
7x11+5x12+6x13+8x21+4x22+9x23+5x31+6x32+4x33=> max
Rozwiązanie:
Stosujemy algorytm węgierski. Ponieważ funkcję celu należy maksymalizować,
musimy wszystkie elementy tabeli 1 pomnożyć przez -1.
Tabela 2. Modyfikacja danych wejściowych
Pracownik/Zestaw Biuro Do gier Stacja graficzna
PI -7 -5 -6
PII -8 -4 -9
PIII -5 -6 -4
W kolejnym kroku musimy doprowadzić do sytuacji, gdy w każdym wierszu i w każdej
kolumnie będzie występować przynajmniej jedno zero.
W tym celu do:
każdego elementu pierwszego wiersza dodajemy wartość najmniejszą (7),
każdego elementu drugiego wiersza dodajemy wartość najmniejszą (9),
każdego elementu trzeciego wiersza dodajemy wartość najmniejszą (6).
Tabela 3. Przekształcone dane
Pracownik/Zestaw Biuro Do gier Stacja graficzna
PI 0 2 1
PII 1 5 0
PIII 1 0 2
Dodano w sumie 22 sztuki komputerów.
Następnie próbujemy dokonać przydziału zadań poszczególnym pracownikom:
Tabela 4. Wyniki przydziału zadań produkcyjnych
Pracownik/Zestaw Biuro Do gier Stacja graficzna
PI 0 2 1
PII 1 5 0
PIII 1 0 2
Jerzy Skrzypek - Kraków 2003
3
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
Uzyskaliśmy rozwiązanie optymalne.
Odpowiedź:
Zespół pracowników może zmontować w czasie dnia roboczego 22 komputery, pod
warunkiem, że:
pierwszy pracownik będzie montował komputery „Biurowe”,
drugi pracownik będzie montował komputery „Stacje graficzne”,
trzeci pracownik będzie montował komputery „Do gier”.
W rezultacie cały zespół zmontuje 7 komputerów „Biurowych”, 9 „Stacji graficznych” i
6 „Do gier”.
3. Wariant B
Pewnego dnia pojawiła się możliwość montowania nowego zestawu:
Profesjonalnego”. W konsekwencji niezbędne było sprawdzenie ile czasu zajmie
montowanie zestawu „Profesjonalnego” poszczególnym pracownikom. Pojawia się,
więc zmodyfikowana tabela.
Tabela 5. Nowe dane
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 7 5 6 4
PII 8 4 9 8
PIII 5 6 4 6
Zmienna decyzyjna
x(i,j) oznacza przydział i-tego pracownika do montażu zestawu j-tego typu.(nadal
przyjmuje ona wartości 0 lub 1).
Model matematyczny
Rozwiązanie zadania z warunkami dodatkowymi, przy pomocy algorytmu
węgierskiego, wymaga, aby ilość pracowników odpowiadała ilości zadań.
Musimy więc wprowadzić fikcyjnego pracownika. Jest więc oczywiste, że fikcyjny
pracowników może zmontować 0 sztuk, każdego z zestawów.
Tabela 6. Nowe dane
Jerzy Skrzypek - Kraków 2003
4
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 7 5 6 4
PII 8 4 9 8
PIII 5 6 4 6
PIV 0 0 0 0
W zamieszczonym poniżej modelu matematycznym, na żółto zaznaczono nowe (w
stosunku do wariantu „A”) elementy.
a)każdy z pracowników może montować tylko jeden zestaw:
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
b)każdy z zestawów może być montowany tylko przez jednego pracownika
x11+x21+x31+x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34+x44=1
Funkcja kryterium: maksymalizacja liczby zmontowanych zestawów w ciągu dnia
pracy:
7x11+5x12+6x13+4x14+8x21+4x22+9x23+8x24++5x31+6x32+4x33+6x34-> max
Stosujemy algorytm węgierski.
Odpowiedź:
Zespół pracowników może zmontować w czasie dnia roboczego 22 komputery, pod
warunkiem, że:
pierwszy pracownik będzie montował komputery „Biurowe”,
drugi pracownik będzie montował komputery „Stacje graficzne”,
trzeci pracownik będzie montował komputery „Do gier”,
czwarty pracownik będzie montował komputery „Profesjonalne”.
W rezultacie cały zespół zmontuje 7 komputerów „Biurowych”, 9 „Stacji graficznych” i
6 „Do gier”, a komputery „Profesjonalne” nie będą montowane.
4. Wariant C
Szef firmy nie jest jednak zadowolony z rozwiązania otrzymanego dla wariantu „B”,
ponieważ na rynku zaczyna się pojawiać popyt na zestawy „Profesjonalne”. Pojawia
Jerzy Skrzypek - Kraków 2003
5
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
się konieczność montowania nowego zestawu: „Profesjonalnego”, kosztem innego
zestawu. W praktyce, oznacza to, że zestaw „Profesjonalny” nie może być
montowany przez czwartego, fikcyjnego pracownika. Pojawia się, więc
zmodyfikowana tabela (M oznacza liczbę o dużej wartości).
Tabela 7. Zmodyfikowane dane
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 7 5 6 4
PII 8 4 9 8
PIII 5 6 4 6
PIV 0 0 0 -M
Model matematyczny
x(i,j) dalej oznacza przydział i-tego pracownika do montażu zestawu j-tego typu.
Model matematyczny jest identyczny jak w przypadku poprzedniego wariantu, poza
jednym, nowym elementem funkcji kryterium.
a)każdy z pracowników może montować tylko jeden zestaw:
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
b)każdy z zestawów może być montowany tylko przez jednego pracownika
x11+x21+x31+x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34+x44=1
Funkcja kryterium: maksymalizacja liczby zmontowanych zestawów w ciągu dnia
pracy:
7x11+5x12+6x13+4x14+8x21+4x22+9x23+8x24+5x31+6x32+4x33+6x34-Mx44>
max
Rozwiązanie:
Stosujemy algorytm węgierski.
Odpowiedź:
Zespół pracowników może zmontować w czasie dnia roboczego 22 komputery, pod
warunkiem, że:
pierwszy pracownik będzie montował komputery „Biurowe”,
Jerzy Skrzypek - Kraków 2003
6
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
drugi pracownik będzie montował komputery „Stacje graficzne”,
trzeci pracownik będzie montował komputery „Profesjonalne”,
czwarty pracownik będzie montował komputery „Do Gier”.
W rezultacie cały zespół zmontuje 7 komputerów „Biurowych”, 9 „Stacji graficznych” i
6 komputerów „Profesjonalnych”. Zestawy „Do gier” nie będą montowane.
5. Wariant D
Okazuje się jednak, że klienci wciąż pytają o zestawy „Do gier”, a więc nie można
zrezygnować z jego montażu. W konsekwencji zatrudniono czwartego pracownika.
Praktyka pokazała jednak, że pracownik „1” nie ma odpowiednich kwalifikacji do
montowania komputerów „Profesjonalnych”, oraz „Stacji graficznych”, a pracownik
„4” ma zbyt wysokie kwalifikacje i aspiracje, aby montować zestawy „Biurowe”.
Pojawia się, więc zmodyfikowana tabela.
Tabela 8. Zmdyfikowane dane
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 7 5 0 0
PII 8 4 9 8
PIII 5 6 4 6
PIV 0 8 10 4
Model matematyczny
x(i,j) oznacza przydział i-tego pracownika do montażu zestawu j-tego typu.
Model matematyczny, poza funkcją celu, nie uległ zmianie.
a)każdy z pracowników może montować tylko jeden zestaw:
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
b)każdy z zestawów może być montowany tylko przez jednego pracownika
x11+x21+x31+x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
Jerzy Skrzypek - Kraków 2003
7
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
x14+x24+x34+x44=1
Funkcja kryterium: maksymalizacja liczby zmontowanych zestawów w ciągu dnia
pracy:
7x11+5x12+0x13+0x14+8x21+4x22+9x23+8x24++5x31+6x32+4x33+6x34+
0x41+8x42+10x43+4x44-> max
Rozwiązanie:
Stosujemy algorytm węgierski.
Odpowiedź:
Zespół pracowników może zmontować w czasie dnia roboczego 31 zestawów
komputerowych, pod warunkiem, że:
pierwszy pracownik będzie montował komputery „Biurowe”,
drugi pracownik będzie montował komputery „Profesjonalne”,
trzeci pracownik będzie montował komputery „Do gier”,
czwarty pracownik będzie montował komputery „Stacje graficzne”.
W rezultacie cały zespół zmontuje 7 komputerów „Biurowych”, 10 „Stacji graficznych”
6 „Do gier”, oraz 8 „Profesjonalnych”.
6. Wariant E
Uchylamy założenie dotyczące faktu, że każdy z pracowników może montować tylko
jeden zestaw komputerowy, a jeden zestaw może być montowany tylko przez
jednego pracownika.
Pracownicy wyspecjalizowali się:
P1-organizuje montaż,
P2-montuje części,
P3-instaluje oprogramowanie,
P4 -testuje zestaw.
Tabela 9. Nowe dane
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 7 5 0 0
PII 8 4 9 8
PIII 5 6 4 6
PIV 0 8 10 4
Jerzy Skrzypek - Kraków 2003
8
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
Przytoczone dane pokazują, że „Stacje graficzne” oraz zestawy „Profesjonalne” nie
wymagają organizacji montażu, a zestawy „Biurowe” nie wymagają testowania.
Należy maksymalizować liczbę komputerów wyprodukowanych w ciągu miesiąca,
przy dodatkowych założeniach:
każdy z pracowników może pracować najwyżej 200 godzin w miesiącu,
należy zmontować przynajmniej 25 sztuk każdego z zestawów.
Model matematyczny
x(i,j) - czas pracy i-tego pracownika przeznaczony na obsługę j-tego zestawu.
a)ograniczenia dotyczące czasu pracy pracowników:
x11+x12+x13+x14=<200
x21+x22+x23+x24=<200
x31+x32+x33+x34=<200
x41+x42+x43+x44=<200
b)ograniczenia dotyczące liczby zmontowanych zestawów:
7x11>=25; 5x12>=25
8x21>=25; 4x22>=25; 9x23>=25; 8x24>=25
5x31>=25; 6x32>=25; 4x33>=25; 6x34>=25
8x42>=25; 10x43>=25; 4x44>=25
Funkcja kryterium:
7x11+5x12+
8x21+4x22+9x23+8x24+
5x31+6x32+4x33+6x34+
8x42+10x43+4x44+> max
Odpowiedź:
W celu uzyskania rozwiązania całkowitoliczbowego, zastosowano algorytm
programowania całkowitoliczbowego. Rozwiązanie optymalne podano w poniższej
tabeli.
Tabela 10. czas pracy i-tego pracownika przy montażu j-tego zestawu
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 195 5 0 0
PII 4 7 185 4
PIII 5 183 7 5
Jerzy Skrzypek - Kraków 2003
9
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
PIV 0 4 189 7
Zostanie wyprodukowanych 6278 zestawów.
7. Wariant F
Uchylamy założenie o specjalizacji pracowników. Każdy z pracowników może, więc
pracować przy kilku zestawach. Załóżmy również, że znany jest popyt na komputery
poszczególnych typów.
Tabela 11. Nowe dane
Pracownik/Zestaw Biuro Do gier Stacja
graficzna
Profesjonalny Czas
pracy
PI 7 5 0 0 200
PII 8 4 9 8 200
PIII 5 6 4 6 200
PIV 0 8 10 4 200
Popyt 200 150 150 5
Model matematyczny
x(i,j) - czas pracy i-tego pracownika przeznaczony na obsługę j-tego zestawu.
a)ograniczenia dotyczące czasu pracy pracowników:
x11+x12+x13+x14=<200
x21+x22+x23+x24=<200
x31+x32+x33+x34=<200
x41+x42+x43+x44=<200
b)ograniczenia dotyczące liczby zmontowanych zestawów:
7x11+8x21+5x31+0x41>=200
5x12+4x22+6x32+8x42>=150
0x13+9x23+4x33+10x43>=150
0x14+8x24+6x34+4x44>=5
Funkcja kryterium:
7x11+5x12+
8x21+4x22+9x23+8x24+
5x31+6x32+4x33+6x34+
8x42+10x43+4x44+> max
Odpowiedź:
Jerzy Skrzypek - Kraków 2003
10
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
W celu uzyskania rozwiązania całkowitoliczbowego, zastosowano algorytm
programowania całkowitoliczbowego. Rozwiązanie optymalne podano w poniższej
tabeli.
Tabela 12. czas pracy i-tego pracownika przy montażu j-tego zestawu
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 200 0 0 0
PII 0 0 200 0
PIII 0 199 0 1
PIV 0 0 200 0
Zostanie wyprodukowanych 6400 zestawów.
8. Wariant G
Załóżmy teraz, że poniższa tabela zawiera czas pracy i-tego pracownika przy
montażu j-tego zestawu komputerowego, a problem polega na minimalizacji czasu
wykonania zadań planowych.
Tabela 13. Kolejna modyfikacja danych
Pracownik/Zestaw Biuro Do gier Stacja
graficzna
Profesjonalny Czas
pracy
PI 7 5 0 0 200
PII 8 4 9 8 200
PIII 5 6 4 6 200
PIV 0 8 10 4 200
Popyt 20 20 20 20
Model matematyczny
x(i,j) - ilość zestawów j-tego typu zmontowana przez i-tego pracownika.
a)ograniczenia dotyczące czasu pracy pracowników:
7x11+5x12+0x13+0x14=<200
8x21+4x22+9x23+8x24=<200
5x31+6x32+4x33+6x34=<200
0x41+8x42+10x43+4x44=<200
b)ograniczenia dotyczące liczby zmontowanych zestawów:
x11+x21+x31+x41>=20
x12+x22+x32+x42>=20
x13+x23+x33+x43>=20
Jerzy Skrzypek - Kraków 2003
11
Kompleksowe zadanie z zakresu przydziału zadań produkcyjnych
x14+x24+x34+x44>=20
Funkcja kryterium:
7x11+5x12+
8x21+4x22+9x23+8x24+
5x31+6x32+4x33+6x34+
8x42+10x43+4x44+> min
Odpowiedź:
W celu uzyskania rozwiązania całkowitoliczbowego, zastosowano algorytm
programowania całkowitoliczbowego. Rozwiązanie optymalne podano w poniższej
tabeli.
Tabela 14. Ilośc j-tych zestawów zmontowana przez i-tego pracownika
Pracownik/Zestaw Biuro Do gier Stacja graficzna Profesjonalny
PI 0 0 0 0
PII 0 20 0 0
PIII 20 0 20 0
PIV 0 0 0 20
Zadania planowe zostaną wykonane w ciągu 340 godzin.
Jerzy Skrzypek - Kraków 2003
12