Algorytmy szeregowania zadań (implementacja w C lub C++)

Jest rok 2222. Mieszkasz na księżycu. Ziemia wybuchła, a Ty pracujesz ciężko każdego dnia, jako brygadier/ka w kopalni kamieni szlachetnych w Cratere De la Rousse.

Jest piękny sobotni wieczór. Waga każdego kamienia spowalnia taczkę, którą blaszane roboty muszą przewieźć i załadować do wagonika.

Kiedy załadunek taczki nadchodzi to Ty musisz zdecydować, który miedziany robot ma ją przeładować. Twoja rola jest bardzo ważna, to Ty jesteś planistą całego przedsięwzięcia.

Zadanie 1 (3 punkty - na zajęciach)

Taczki mogą nadejść w kolejnych minutach. Spiesz się, żeby żadnej nie przegapić! Wczytaj dane wejściowe z plików.

W każdej linii

• pierwsza liczba oznacza minutę nadejścia taczek
• występuje pewna liczba trójek oznaczających
  • numer taczki
  • rodzaj kamieni
  • wagę każdego kamienia
  • ilość kamieni na taczce
• Liczba minut, które są potrzebne aby przeładować taczkę jest iloczynem wagi kamieni i ich ilości

np.

0 1 gold 1 2 
1 2 rubies 3 1 3 agates 1 2
2 4 turquoise 1 2

oznacza że:

• w minucie 0 pojawiła się taczka numer 1 zawierające 1 złoty kamień o wadze 2 - potrzeba 2 minuty aby ją przeładować
• w minucie 1 pojawiły się 2 taczki:
  • taczka numer 2 zawierająca 3 rubiny o wadze 1 - potrzeba 3 minut, żeby ją zawieźć
  • taczka numer 3 zawierająca 1 agat o wadzie 2 - potrzeba 2 minut, żeby ją zawieźć
• w minucie 2 pojawiła się taczka numer 4, zawierająca 1 turkus o wadze 2

Wczytaj dane z plików: Dane 1 i wyświetl na ekranie.

Zadanie 2 (3 punkty - na zajęciach)

Dobra robota. Już potrafisz rozpoznawać kiedy nadchodzi nowa taczka i wiesz jak długo zajmie jej wyładunek.

W kopalni la Carotte pracuje tylko 1 miedziany robot. W kopalni la Betterave 2 miedziane roboty. W kopalni le Radis jest zawsze dużo roboty, więc może pracować nawet do 6 miedzianych robotów.

W swojej pracy nie rozstajesz się ze swoim kajetem. Zawsze zapisujesz w nim które taczki czekają na swoją kolej i obserwujesz otoczenie aby reagować od razu gdy nowe taczki pojawią się na horyzoncie.

Zaplanuj pracę robotów według następujących zasad:

Wykorzystaj strategię FCFS (First-Come, First-Served):

• wybieraj dla kolejnych robotów taczki z kajetu w takiej kolejności w jakiej są do niego wpisywane (FIFO)
• wyglądaj kolejnych taczek, notując ich przybycie w kajecie

Dla powyższych danych wejściowych w kopalni la Betterave (2 miedziane roboty) planista wykona następujące operacje:

2 robots in the mine

FCFS:

Moment 0

        wheelbarrow arrived <1 gold 1 2 [2]>
                [gold        2][             ]
Moment 1
        wheelbarrow arrived <2 rubies 3 1 [3]>
        wheelbarrow arrived <3 agates 1 2 [2]>
                [gold        1][rubies      3]
Moment 2
        wheelbarrow arrived <4 turquoise 1 2 [2]>
                [agates      2][rubies      2]
Moment 3
                [agates      1][rubies      1]
Moment 4
                [turquoise   2][             ]
Moment 5
                [turquoise   1][             ]

Dla kopalni le Radis wynik szeregowania będzie następujący:

6 robots in the mine

FCFS:

Moment 0
        wheelbarrow arrived <1 gold 1 2 [2]>
                [gold        2][             ][             ][             ][             ][             ]
Moment 1
        wheelbarrow arrived <2 rubies 3 1 [3]>
        wheelbarrow arrived <3 agates 1 2 [2]>
                [gold        1][rubies      3][agates      2][             ][             ][             ]
Moment 2
        wheelbarrow arrived <4 turquoise 1 2 [2]>
                [turquoise   2][rubies      2][agates      1][             ][             ][             ]
Moment 3
                [turquoise   1][rubies      1][             ][             ][             ][             ]

Zadanie 3 (4 punkty - na zajęciach, lub 2 punkty - w domu)

Brawo masz już zaliczoną listę! Gratuluję. Teraz czas zastosować inną strategię planowania. Niech będzie to RR (Round-Robin). Oddychasz z ulgą - na szczęście na wykładzie z Twojego ulubionego przedmiotu ten algorytm został omówiony!

Zaimplementuj następujący sposób planowania pracy robotów:

• w kajecie zapisujesz kolejno przybyłe taczki w kolejności nadejścia
• każdy robot opróżnia taczki przez określony kwant czasu (np. przez kilka minut) następnie przerywa pracę i zostaje mu przydzielone nowe zadanie z początku kolejki taczek gotowych do wyładowania w kajecie
• jeśli taczka nie została opróżniona, to po upływie kwantu czasu taczka zostaje wpisana na koniec kolejki w kajecie
• zwróć uwagę, by nowo przybyłe taczki dopisywane były na koniec kolejki, po jej zaktualizowaniu dla istniejących już taczek!!

Dla tej strategii wynik obliczeń w kopalni dla 2 miedzianych robotów oraz kwantu czasu wynoszącego minutę będzie następujący:

2 robots in the mine

RR with quantum 1:

Moment 0
        wheelbarrow arrived <1 gold 1 2 [2]>
                [gold        2][             ]
Moment 1
        wheelbarrow arrived <2 rubies 3 1 [3]>
        wheelbarrow arrived <3 agates 1 2 [2]>
                [gold        1][rubies      3]
Moment 2
        wheelbarrow arrived <4 turquoise 1 2 [2]>
                [agates      2][rubies      2]
Moment 3
                [turquoise   2][agates      1]
Moment 4
                [rubies      1][turquoise   1]

Dla kwantu czasu o wartości 2 wynik będzie następujący:

2 robots in the mine

RR with quantum 2:

Moment 0
        wheelbarrow arrived <1 gold 1 2 [2]>
                [gold        2][             ]
Moment 1
        wheelbarrow arrived <2 rubies 3 1 [3]>
        wheelbarrow arrived <3 agates 1 2 [2]>
                [gold        1][rubies      3]
Moment 2
        wheelbarrow arrived <4 turquoise 1 2 [2]>
                [agates      2][rubies      2]
Moment 3
                [agates      1][turquoise   2]
Moment 4
                [rubies      1][turquoise   1]

Zadanie 4 (4 punkty - tylko na zajęciach)

Podane na zajęciach przez prowadzącego.

Wymagania

1. Program otrzyma dane dotyczące strategii szeregowania w argumentach wywołania. Pierwszy argument określa liczbę robotów dostępnych do rozładowania taczek. Drugi argument zadaje kwant czasu pracy robota nad jedną taczką (parametr ten ma znaczenie tylko dla strategii RR i musi mieć wartość co najmniej 1). Trzeci argument wywołania podaje nazwę pliku danych wejściowych. Jeśli jest on równy znakowi '-' (minus), to dane wejściowe należy czytać ze standardowego wejścia a nie z pliku. Czwarty argument zadaje algorytm szeregowania w postaci kodu liczbowego: 1 = RR, 2 = FCFS.
2. Postaraj się sformatować wyjście programu dokładnie tak, jak w udostępnionych poniżej przykładach. Jeśli program będzie wyświetlał wyniki w innym formacie, to może otrzymać za to karę w ocenie (ujemne punkty).
3. Jeśli program będzie generował wyniki niezgodne z przykładowymi wynikami dostępnymi na podanej niżej stronie to proszę odnotować to w raporcie. Proszę nie przysyłać całych plików wynikowych.
4. Program ma działać w trybie krokowym. Oznacza to, że po wczytaniu każdego pojedynczego wiersza powinien od razu obliczyć i wyświetlić na wyjściu decyzję planisty dotyczącą bieżącego momentu czasu.
5. Porównaj harmonogramy wygenerowane przy użyciu zadanych strategii. W porównaniu użyj znanych Ci kryteriów jakości szeregowania. Które strategie można uznać za najlepsze, a które za najgorsze?

Przykłady

Więcej przykładowych danych znajdziesz Tutaj.

Zdjęcia pochodzą z vecteezy:

Kopalnia

Robot