« zpět / back

RDU - rozvrhování úlohy open-shop

Rozvrhování úloh v nákladní dopravě – projekt ČVUT FEL

2003

K335,2003

David Šilhan,[email protected]

Zadání

Navrhněte a naprogramujte vhodný algoritmus pro nepreemptivní rozvrhování v nákladní automobilové dopravě. Dopravce má k dispozici m dopravních prostředků které mají provést rozvoz materiálu podle předloženého plánu. Každá zakázka má definovanou mezní dobu dopravení na místo určení.

Vstupy
m ... počet procesorů Pm
Tn ... seznam spojů v grafu

u každého spoje Tn je dáno:
Xj ... výchozí uzel
Yj ... cílový uzel
dj ... due date ... okamžik požadovaného dokončení
pj ... doba vykonávání, se určuje ze vzdálenosti cílů, které jsou dány souřadnicemi x,y kt. nabývají hodnot x=(xmin,xmax),y=(ymin,ymax)
doba vykonávání úkolu je přímo úměrná vzdálenosti mezi místy a pokud není nalezen spoj přímo předešlý na předcházející, je tato vzdálenost prodloužena o dobu potřebnou na manipulační přejezd.

Rozvrhovat budeme úkoly jako nepřerušitelný / nepreemptivní rozvrh.

Výstupy
tj ... začátek vykonávání jednotlivých úkolů a určení čísla m procesoru Pm na kterém se úkol bude vykonávat

Dále zjištěné: cj ... completion time (okamžik dokončení) Lj ... Lj=Cj-dj ... lateness (zpoždění)


Algoritmus
Algoritmus pro řešní rozvrhování na paraleleních procesorech,
P | 0 < pj < pmax | sum(Lmax)
P ... identical processors
b1 ... - (no preemption is allowed)
b2 ... - (no additoinal resources exist)
b3 ... - (no precedence constraints)
b4 ... - (all ready times are zero)
b5 ... 0 < pj < pmax (processing times are limited from top by the maximal distance between destinations)
b6 ... - (no deadlines, but the due dates are used)
b7 ... - (not a job-shop)
b8 ... - (there is no wait-property there)

Vyšel jsem z algoritmu LPT (Longest processing times), kde jsem však jako kritérium podle nějž bude rozvrhování probíhat zvolil due date. Tedy první volný úkol s nejbližším časem dokončení bude přiřazen prvnímu volnému procesoru z m procesorů. Algoritmus jsem upravil o hledání nejbližšího úkolu jehož režie na přesun z místa dokončení předchozího úkolu do místa započtí úklu následujícího by byla nižší. Délka prohledávání v uspořádaném seznamu podle "due date" je omezena nastavením konstanty DDLIMIT, která určuje maximální změnu due date úkolu oproti prvnímu volnému úkolu v seznamu po který ze bude levnější úkol vyhledávat.


Algoritmus pracuje v několika krocích po načtení dat do lineárního seznamu jsou tato data setříděna pomocí algoritmu Quick sort jehož složitost je O(n)=n.log(n) vzestupně podle požadované doby dokončení duedate. Funkcí kterou budeme minimalizovat je celkové zpoždění zadaných úkolů Tardiness, které zachycuje jen kladná zpoždění, tj. nesplněné termíny dokončení.

Prvních j-úkolů přiřadím k vykonávání jednotlivým procesorům s počátkem v čase 0 (resp. v "time") Současně již zde určím zpoždění prvních j úkolů.

ukazatel = 0 //ukazatel v seřazeném seznamu cest
while not konec_seznamu {
    najdi procesor s nejbližší dobou dokončení úkolu
    time= nejzazší čas dokončení prvního úkolu z j
    tardiness=time-duedate
    DLIMIT=0..10..40
    projdi prvních n prvků následujících za následujícím pokud se deadline změní max o DDLIMIT
        z těchto prvků zvol prvek s nejmenší vzdáleností (pokutovou funkcí)
         od aktuální polohy právě dokončeného procesu
        pokud je prvek s nejmenší vzdáleností jiný než původně aktuální na prvním místě
        prohoď tento s prvkem nalezeným
        tj. na první pozici bude nyní nejbližší navazující cesta.
    nalezenému procesoru přiřaď úkol na první pozici od aktuálního ukazatele
    ukazatel ++
konec

Složitost:
q-chyba LPT podle počtu procesorů m Nejsložitější operací je třídění seznamu jehož složitost je O( n.log n )

Složitost hledání dalšího úkolu podle ceny s ohledem na DDLIMIT je v nejhorším případě a při nevhodně nastaveném DDLIMIT O( n. log n ) avšak v praxi nastavíme zkoumané okénko na fixní hodnotu kdy potom složitost bude O( n ).

Pro LPT bylo zjištěno, že nalezené suboptimální řešení je v nejhorším případě q-krát horší než optimální, kde
q= 1,333 - 0,333/m
kde m je počet procesorů.

Zdrojové soubory:

Porovnání zjištěných výsledků a vliv nastavní mezí DDLIMIT

Tabulka se zachycením závislosti procesního času na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Tabulka se zachycením závislosti procesního času ve všech procesorech na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Tabulka se zachycením závislosti lateness na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Tabulka se zachycením závislosti tardiness na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Graf závislosti tardiness na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Graf závislosti lateness na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Graf závislosti tardiness na počtu použitých procesorů a velikosti DDLIMIT
RDU-image (table/graph)

Ukázka z výběru prvního uvolněného procesoru pro volbu Pm, m=6
*P[0] nodeid=3, duedate=0.7071067811865476, procNo=4
*P[1] nodeid=1, duedate=0.728201595557988, procNo=2
*P[2] nodeid=5, duedate=0.8944271909999159, procNo=6
*P[3] nodeid=4, duedate=0.9860089226269497, procNo=5
*P[4] nodeid=0, duedate=1.2649110640673518, procNo=1
*P[5] nodeid=2, duedate=1.5268827230335917, procNo=3
getting PID 4 at time 0.0
*P[0] nodeid=1, duedate=0.728201595557988, procNo=2
*P[1] nodeid=5, duedate=0.8944271909999159, procNo=6
*P[2] nodeid=4, duedate=0.9860089226269497, procNo=5
*P[3] nodeid=0, duedate=1.2649110640673518, procNo=1
*P[4] nodeid=6, duedate=1.3395623132202235, procNo=4
*P[5] nodeid=2, duedate=1.5268827230335917, procNo=3
getting PID 2 at time 0.7071067811865476
*P[0] nodeid=5, duedate=0.8944271909999159, procNo=6
*P[1] nodeid=4, duedate=0.9860089226269497, procNo=5
*P[2] nodeid=7, duedate=1.175415191057946, procNo=2
*P[3] nodeid=0, duedate=1.2649110640673518, procNo=1
*P[4] nodeid=6, duedate=1.3395623132202235, procNo=4
*P[5] nodeid=2, duedate=1.5268827230335917, procNo=3
getting PID 6 at time 0.728201595557988
*P[0] nodeid=4, duedate=0.9860089226269497, procNo=5
*P[1] nodeid=7, duedate=1.175415191057946, procNo=2
*P[2] nodeid=0, duedate=1.2649110640673518, procNo=1
*P[3] nodeid=6, duedate=1.3395623132202235, procNo=4
*P[4] nodeid=8, duedate=1.4645149035494849, procNo=6
*P[5] nodeid=2, duedate=1.5268827230335917, procNo=3
getting PID 5 at time 0.8944271909999159
*P[0] nodeid=7, duedate=1.175415191057946, procNo=2
*P[1] nodeid=0, duedate=1.2649110640673518, procNo=1
*P[2] nodeid=6, duedate=1.3395623132202235, procNo=4
*P[3] nodeid=8, duedate=1.4645149035494849, procNo=6
*P[4] nodeid=2, duedate=1.5268827230335917, procNo=3
*P[5] nodeid=9, duedate=1.5560966351765186, procNo=5
getting PID 2 at time 0.9860089226269497
*P[0] nodeid=0, duedate=1.2649110640673518, procNo=1
*P[1] nodeid=6, duedate=1.3395623132202235, procNo=4
*P[2] nodeid=8, duedate=1.4645149035494849, procNo=6
*P[3] nodeid=2, duedate=1.5268827230335917, procNo=3
*P[4] nodeid=10, duedate=1.5289685816512197, procNo=2
*P[5] nodeid=9, duedate=1.5560966351765186, procNo=5
getting PID 1 at time 1.175415191057946
*P[0] nodeid=6, duedate=1.3395623132202235, procNo=4
*P[1] nodeid=8, duedate=1.4645149035494849, procNo=6
*P[2] nodeid=2, duedate=1.5268827230335917, procNo=3
*P[3] nodeid=10, duedate=1.5289685816512197, procNo=2
*P[4] nodeid=9, duedate=1.5560966351765186, procNo=5
*P[5] nodeid=11, duedate=1.6184644546606255, procNo=1
getting PID 4 at time 1.2649110640673518
*P[0] nodeid=12, duedate=1.3395623132202235, procNo=4
*P[1] nodeid=8, duedate=1.4645149035494849, procNo=6
*P[2] nodeid=2, duedate=1.5268827230335917, procNo=3
*P[3] nodeid=10, duedate=1.5289685816512197, procNo=2
*P[4] nodeid=9, duedate=1.5560966351765186, procNo=5
*P[5] nodeid=11, duedate=1.6184644546606255, procNo=1
getting PID 4 at time 1.3395623132202235
*P[0] nodeid=8, duedate=1.4645149035494849, procNo=6
*P[1] nodeid=2, duedate=1.5268827230335917, procNo=3
*P[2] nodeid=10, duedate=1.5289685816512197, procNo=2
*P[3] nodeid=9, duedate=1.5560966351765186, procNo=5
*P[4] nodeid=11, duedate=1.6184644546606255, procNo=1
*P[5] nodeid=13, duedate=2.233989504220139, procNo=4
getting PID 6 at time 1.3395623132202235
*P[0] nodeid=2, duedate=1.5268827230335917, procNo=3
*P[1] nodeid=10, duedate=1.5289685816512197, procNo=2
*P[2] nodeid=9, duedate=1.5560966351765186, procNo=5
*P[3] nodeid=11, duedate=1.6184644546606255, procNo=1
*P[4] nodeid=14, duedate=1.7807426695663229, procNo=6
*P[5] nodeid=13, duedate=2.233989504220139, procNo=4
getting PID 3 at time 1.4645149035494849
*P[0] nodeid=10, duedate=1.5289685816512197, procNo=2
*P[1] nodeid=9, duedate=1.5560966351765186, procNo=5
*P[2] nodeid=11, duedate=1.6184644546606255, procNo=1
*P[3] nodeid=14, duedate=1.7807426695663229, procNo=6
*P[4] nodeid=15, duedate=2.096970435583161, procNo=3
*P[5] nodeid=13, duedate=2.233989504220139, procNo=4
getting PID 2 at time 1.5268827230335917
*P[0] nodeid=9, duedate=1.5560966351765186, procNo=5
*P[1] nodeid=11, duedate=1.6184644546606255, procNo=1
*P[2] nodeid=16, duedate=1.7525753794011987, procNo=2
*P[3] nodeid=14, duedate=1.7807426695663229, procNo=6
*P[4] nodeid=15, duedate=2.096970435583161, procNo=3
*P[5] nodeid=13, duedate=2.233989504220139, procNo=4
getting PID 5 at time 1.5289685816512197
*P[0] nodeid=11, duedate=1.6184644546606255, procNo=1
*P[1] nodeid=16, duedate=1.7525753794011987, procNo=2
*P[2] nodeid=14, duedate=1.7807426695663229, procNo=6
*P[3] nodeid=17, duedate=2.0033102306764765, procNo=5
*P[4] nodeid=15, duedate=2.096970435583161, procNo=3
*P[5] nodeid=13, duedate=2.233989504220139, procNo=4
getting PID 1 at time 1.5560966351765186
*P[0] nodeid=16, duedate=1.7525753794011987, procNo=2
*P[1] nodeid=14, duedate=1.7807426695663229, procNo=6
*P[2] nodeid=18, duedate=1.8420712524106044, procNo=1
*P[3] nodeid=17, duedate=2.0033102306764765, procNo=5
*P[4] nodeid=15, duedate=2.096970435583161, procNo=3
*P[5] nodeid=13, duedate=2.233989504220139, procNo=4
getting PID 2 at time 1.6184644546606255
*P[0] nodeid=14, duedate=1.7807426695663229, procNo=6
*P[1] nodeid=18, duedate=1.8420712524106044, procNo=1
*P[2] nodeid=17, duedate=2.0033102306764765, procNo=5
*P[3] nodeid=15, duedate=2.096970435583161, procNo=3
*P[4] nodeid=13, duedate=2.233989504220139, procNo=4
*P[5] nodeid=19, duedate=2.3579028579095755, procNo=2
getting PID 6 at time 1.7525753794011987
*P[0] nodeid=18, duedate=1.8420712524106044, procNo=1
*P[1] nodeid=17, duedate=2.0033102306764765, procNo=5
*P[2] nodeid=15, duedate=2.096970435583161, procNo=3
*P[3] nodeid=13, duedate=2.233989504220139, procNo=4
*P[4] nodeid=19, duedate=2.3579028579095755, procNo=2
*P[5] nodeid=20, duedate=2.5815096556595547, procNo=6
getting PID 1 at time 1.7807426695663229
*P[0] nodeid=17, duedate=2.0033102306764765, procNo=5
*P[1] nodeid=15, duedate=2.096970435583161, procNo=3
*P[2] nodeid=21, duedate=2.158299018427442, procNo=1
*P[3] nodeid=13, duedate=2.233989504220139, procNo=4
*P[4] nodeid=19, duedate=2.3579028579095755, procNo=2
*P[5] nodeid=20, duedate=2.5815096556595547, procNo=6
getting PID 5 at time 1.8420712524106044
*P[0] nodeid=15, duedate=2.096970435583161, procNo=3
*P[1] nodeid=21, duedate=2.158299018427442, procNo=1
*P[2] nodeid=13, duedate=2.233989504220139, procNo=4
*P[3] nodeid=19, duedate=2.3579028579095755, procNo=2
*P[4] nodeid=22, duedate=2.5149775042781695, procNo=5
*P[5] nodeid=20, duedate=2.5815096556595547, procNo=6
getting PID 3 at time 2.0033102306764765
*P[0] nodeid=21, duedate=2.158299018427442, procNo=1
*P[1] nodeid=13, duedate=2.233989504220139, procNo=4
*P[2] nodeid=19, duedate=2.3579028579095755, procNo=2
*P[3] nodeid=22, duedate=2.5149775042781695, procNo=5
*P[4] nodeid=20, duedate=2.5815096556595547, procNo=6
*P[5] nodeid=23, duedate=3.3449510171763506, procNo=3
getting PID 1 at time 2.096970435583161
*P[0] nodeid=13, duedate=2.233989504220139, procNo=4
*P[1] nodeid=19, duedate=2.3579028579095755, procNo=2
*P[2] nodeid=22, duedate=2.5149775042781695, procNo=5
*P[3] nodeid=20, duedate=2.5815096556595547, procNo=6
*P[4] nodeid=24, duedate=2.9519935287269905, procNo=1
*P[5] nodeid=23, duedate=3.3449510171763506, procNo=3
getting PID 4 at time 2.158299018427442
*P[0] nodeid=19, duedate=2.3579028579095755, procNo=2
*P[1] nodeid=22, duedate=2.5149775042781695, procNo=5
*P[2] nodeid=20, duedate=2.5815096556595547, procNo=6
*P[3] nodeid=24, duedate=2.9519935287269905, procNo=1
*P[4] nodeid=23, duedate=3.3449510171763506, procNo=3
*P[5] nodeid=25, duedate=3.3741649293192775, procNo=4
getting PID 2 at time 2.233989504220139
*P[0] nodeid=22, duedate=2.5149775042781695, procNo=5
*P[1] nodeid=20, duedate=2.5815096556595547, procNo=6
*P[2] nodeid=26, duedate=2.9279905704591447, procNo=2
*P[3] nodeid=24, duedate=2.9519935287269905, procNo=1
*P[4] nodeid=23, duedate=3.3449510171763506, procNo=3
*P[5] nodeid=25, duedate=3.3741649293192775, procNo=4
getting PID 5 at time 2.3579028579095755
*P[0] nodeid=20, duedate=2.5815096556595547, procNo=6
*P[1] nodeid=26, duedate=2.9279905704591447, procNo=2
*P[2] nodeid=24, duedate=2.9519935287269905, procNo=1
*P[3] nodeid=23, duedate=3.3449510171763506, procNo=3
*P[4] nodeid=25, duedate=3.3741649293192775, procNo=4
*P[5] nodeid=27, duedate=3.409404695278085, procNo=5
getting PID 6 at time 2.5149775042781695
*P[0] nodeid=26, duedate=2.9279905704591447, procNo=2
*P[1] nodeid=24, duedate=2.9519935287269905, procNo=1
*P[2] nodeid=28, duedate=3.0287232511595126, procNo=6
*P[3] nodeid=23, duedate=3.3449510171763506, procNo=3
*P[4] nodeid=25, duedate=3.3741649293192775, procNo=4
*P[5] nodeid=27, duedate=3.409404695278085, procNo=5
getting PID 2 at time 2.5815096556595547

Zhodnocení:
Z dosažených výsledků je zřejmé, že se použitým algoritmem podařilo získat vhodný rozvrh v přijatelném čase díky jednoduchosti použité heuristiky. Otázkou zůstává zda by se podařilo najít takový algoritmus, který by elegantněji kladl důraz na vyřešení problému obchodního cestujícího s ohledem na uvažovanou prioritu na optimalizaci podle času splnění (duedate). Při použití uvedeného algoritmu je nutno citlivě zvolit velikost konstanty DDLIMIT na které závisí optimalita nalezeného řešení v procesním čase i v dosaženém zpoždění (tardiness). Při volbě malého DDLIMIT získáváme rozvrh s menším zpožděním a naopak při vyšších hodnotách DDLIMIT je rozvrh optimálnější z hlediska času vykonávání resp. v našem případě ujetými kilometry a v důsledku minimalizací přejezdů mezi cílem předchozího úkolu a počátečním místem úkolu nového (tj. trasa, kdy jede vůz v režii nenaložen).

home


e-mail: david [zavináč] kvik [tečka] cz