Witam wszystkich serdecznie.
Mam niewielki problem z wymyśleniem spójnego algorytmu który wykonywałby pewne zadanie i w związku z tym mam do kolegów i koleżanek takie pytanie; czy może ktoś się z czymś takim spotkał, lub robił coś podobnego w przeszłości.
Problem polega na wykonaniu określonych czynności, przez jak najmniejszą liczbę osób, na podstawie listy zadań.
Oto przykład :
Mamy do posprzątania biurowiec, który ma pięć pięter. Na każdym piętrze są przewidziane do wykonania jakieś czynności na które jest przeznaczony odpowiedni czas. Cały problem polega na tym, że niektóre czynności (chociaż nie wszystkie) mogą być wykonywane tylko w określonym czasie.
I tak, np. :
1. wysypywanie pojemników na śmieci - czas wykonania jednej czynności 15 minut, liczba potrzebnych pracowników - 1 osoba.
2. czyszczenie kubków po kawie/herbacie - czas wykonania 10 minut, liczba potrzebnych pracowników - 1 osoba
3. mycie okien - czas wykonywania 120 minut, liczba pracowników - 3 osoby
4. .... itd, itp....
A teraz utrudnienie, np. :
Na wszystkich piętrach 1-5 można wyrzucać kosze tylko w godzinach od 6:00 do 7:00
Na wszystkich piętrach 1-5 można myć kubki tylko od 8:00 do 9:00
Na pietrach 1,2 i 3 - kawę można robić tylko pomiędzy 10:00 i 11:00
Na piętrach 4 i 5 można robić kawę cały dzień, bez żadnych ograniczeń czasowych, ale dokładnie 3 razy dziennie
Na wszystkich piętrach 1-5 można myć okna tylko od godziny 17:00 do 20:00
Liczba poszczególnych czynności, przypadających na każde piętro jest zmienna, może się zdarzyć, że nie potrzeba zupełnie nic robić.
Przyjmijmy, że liczba pracowników jest nieograniczona oraz, że każde zadanie musi być wykonane a pracownicy mogą poruszać się dowolnie pomiędzy piętrami.
Teraz chodzi o to, żeby w zadanych ramach czasowych i przy użyciu jak najmniejszej liczby pracowników, wykonać wszystkie zadane czynności na każdym piętrze.
Trochę się rozpisałem, ale wydaje mi się, że dość dokładnie opisałem problem
Jeżeli ktoś miał styczność z takim lub podobnym problemem, to bardzo proszę o jakieś podpowiedzi. Język programowania nie ma znaczenia, bardziej chodzi o metodologię.
Z góry dziękuje, Arnoldziq
Mam niewielki problem z wymyśleniem spójnego algorytmu który wykonywałby pewne zadanie i w związku z tym mam do kolegów i koleżanek takie pytanie; czy może ktoś się z czymś takim spotkał, lub robił coś podobnego w przeszłości.
Problem polega na wykonaniu określonych czynności, przez jak najmniejszą liczbę osób, na podstawie listy zadań.
Oto przykład :
Mamy do posprzątania biurowiec, który ma pięć pięter. Na każdym piętrze są przewidziane do wykonania jakieś czynności na które jest przeznaczony odpowiedni czas. Cały problem polega na tym, że niektóre czynności (chociaż nie wszystkie) mogą być wykonywane tylko w określonym czasie.
I tak, np. :
1. wysypywanie pojemników na śmieci - czas wykonania jednej czynności 15 minut, liczba potrzebnych pracowników - 1 osoba.
2. czyszczenie kubków po kawie/herbacie - czas wykonania 10 minut, liczba potrzebnych pracowników - 1 osoba
3. mycie okien - czas wykonywania 120 minut, liczba pracowników - 3 osoby
4. .... itd, itp....
A teraz utrudnienie, np. :
Na wszystkich piętrach 1-5 można wyrzucać kosze tylko w godzinach od 6:00 do 7:00
Na wszystkich piętrach 1-5 można myć kubki tylko od 8:00 do 9:00
Na pietrach 1,2 i 3 - kawę można robić tylko pomiędzy 10:00 i 11:00
Na piętrach 4 i 5 można robić kawę cały dzień, bez żadnych ograniczeń czasowych, ale dokładnie 3 razy dziennie
Na wszystkich piętrach 1-5 można myć okna tylko od godziny 17:00 do 20:00
Liczba poszczególnych czynności, przypadających na każde piętro jest zmienna, może się zdarzyć, że nie potrzeba zupełnie nic robić.
Przyjmijmy, że liczba pracowników jest nieograniczona oraz, że każde zadanie musi być wykonane a pracownicy mogą poruszać się dowolnie pomiędzy piętrami.
Teraz chodzi o to, żeby w zadanych ramach czasowych i przy użyciu jak najmniejszej liczby pracowników, wykonać wszystkie zadane czynności na każdym piętrze.
Trochę się rozpisałem, ale wydaje mi się, że dość dokładnie opisałem problem
Jeżeli ktoś miał styczność z takim lub podobnym problemem, to bardzo proszę o jakieś podpowiedzi. Język programowania nie ma znaczenia, bardziej chodzi o metodologię.
Z góry dziękuje, Arnoldziq
