Úloha permutačního rozvrhování

Autor textu: Radek Mařík
Úprava: Tibor Strašrybka

Odevzdávají se následující soubory v jednom zip archivu:

1. Zdrojový soubor programu řešící rozvrhovací úlohu. Úlohu naprogramujte v Javě ve vývojovém prostředí NetBeans.
2. Soubor se vstupními daty, viz následující zadání.
3. Soubor s výsledky dle následujících pokynů:
   1. Seznam s počátečním rozvrhem
   2. Seznam s dobami trvání jednotlivých úloh $p_j$
   3. Seznam s termíny dokončení $d_j$
   4. Seznam s váhami jednotlivých úloh $w_j$
   5. Pro každý krok hledání nejlepší rozvrh s jeho cenou
   6. Nejlepší nalezený rozvrh s jeho cenou

Všechny úlohy vychází s následujícího textového zadání rozvrhovací úlohy:

1. Jedná se permutační rozvrhování na jednom stroji $1|d_j|\sum w_j \cdot T_j$
2. Úkolem je najít optimální rozvrh pomocí metody tabu prohledávání.

Doporučujeme odladit úlohu na vlastních datech menšího rozsahu.

• Optimalizační kritérium: minimalizace celkového nezáporného zpoždění.
• Okolí rozvrhu: všechny rozvrhy získané párovou výměnou sousedních úloh.
• Výběr rozvrhu z okolí: v každém kroku se vybírá nejlepší rozvrh z okolí.
• Tabu seznam: páry úloh, které byly přehozeny při posledních 11 změnách.
• Celkový počet úloh je 15 se jmény 1 až 15.
• Doby trvání úloh jsou: 4, 16, 6, 5, 9, 19, 1, 13, 12, 20, 20, 19, 5, 18, 12
• Termíny dokončení úloh jsou: 36, 67, 105, 53, 77, 124, 194, 157, 25, 202, 43, 61, 5, 7, 8
• Váhy úloh jsou: 21, 45, 35, 73, 1, 28, 21, 14, 76, 70, 51, 23, 69, 62, 80
• Počáteční rozvrh je: 2, 3, 15, 6, 5, 10, 8, 7, 13, 14, 1, 4, 12, 9, 11
• Proveďte 200 iterací.