Algorytm mrówkowy i szeregowanie zadań

0

Witam,
Mam taki problem. Otóż mam za zadanie napisać program który ma rozwiązać problem szeregowania zadań. Muszę przy tym użyć algorytmu mrówkowego. Wcześniej do szeregowania zadań zawsze używałem algorytmu B&B.
Zasadę działania algorytmu znam, google dostarcza dużo materiału na ten temat. Jednak mam problem ze sposobem implementacji.

W B&B przechodzenie po zadaniach było zrobione za pomocą permutacji, zadania były zapisywane na listach. Z tego co wyczytałem w AOC zadania też powinny być przechowywane na listach:

lista_B - lista nieuporządkowana
lista_A - lista uporządkowana

Dla przykładu zakładam że mam 10 zadań do uporządkowania.
Po przejściu przez zadanie i, zadanie to jest przesuwane z lista_B do lista_A.
Kolejne zadanie jest wybierane losowo. Tutaj jest moje pierwsze pytanie. Czy skoro wybieramy losowo zadanie to czy nie lepiej zrobić to na tablicy? W liście przy wylosowaniu np.8 zadania, trzeba będzie przejść po liście do tego zadania.
Drugie pytanie dotyczy śladu feromonu. Gdzie i jak jest najlepiej zapisywać te dane? Na początku myślałem o stworzeniu tablicy o wielkości [ilość_zadań][ilość_zadań], gdzie kolumny by znaczyły numer zadania a wiersze na której pozycji jest zadanie. I tak będą np. w 3 kroku, przeglądam 3 wiersz tabeli i patrze które zadanie ma najmocniejszy feromon. Tylko tutaj występują pewne trudności: Najmocniejszy feromon może mieć zadanie które już jest na pozycji 2. Przydałoby się jakoś te zadanie wykluczyć z poszukiwań...z tego powodu myślę że tablica jednak nie jest dobrym pomysłem. W takim razie jestem tutaj w kropce, gdyż nie jak na razie nie mam innego pomysłu.

Może ja całkowicie źle myślę nad tym algorytmem.
Poradźcie mi co z tym fantem zrobić

0

Musisz utworzyć z zadań graf kompletny łącząc czyli najlepiej macierz [ilość_zadań][ilość_zadań].

  1. Struktury danych i ich inicjalizacja

    macierz - każda komórka macierzy (krawędź grafu) musi zawierać ilość feromonu, na wstępie wypełnij ją jednolicie identyczną wartością większą od zera

    tablica zadań - każda komórka zawiera informacje o zadaniu - minimalny czas rozpoczęcia, maksymalny czas zakończenia, czas wykonania zadania oraz informacje o tym, czy zadanie zostało zrealizowane przez aktualnie chodzącą mrówkę

    lista zadań - lista tworzona w trakcie wędrówki mrówki, każda mrówka niech zawiera po jednej takiej liście.

  2. Koszt trasy

Koszt trasy którą pokonała mrówka można reprezentować jako suma przekroczeń limitów zakończenia zadań. Suma może być ważona tj. każde zadanie może posiadać wagę z jaką sumowany jest overtime (zakończenie jednych zadań na czas może być ważniejsze od innych). Od sumy również odejmuj całkowity czas na wykonanie wszystkich zadań (też z jakąś rozsądną wagą najlepiej dobraną doświadczalnie).

  1. Trasa mrówki
    Do wszystkich zadań dodaj również zadanie startu - o zerowym czasie trwania.
    Każda mrówka zaczyna od zadania startowego.
    W kolejnym kroku mrówka wybiera nieodwiedzonego sąsiada z prawdopodobieństwem zgodnym z ilością pozostawionego feromonu. Trasa jest zapisywana na liście i na bieżąco jest obliczany jej koszt: do całkowitego czasu wszystkich zadań dodaj ilość czasu jaki musimy czekać aby rozpocząć zadanie oraz czas jego trwania. Do kosztu dodajesz overtime.

1 użytkowników online, w tym zalogowanych: 0, gości: 1