Disjunktivní graf - Disjunctive graph - Wikipedia

V matematické modelování z plánování pracovního obchodu problémy, disjunktivní grafy jsou způsob modelování systému úkolů, které mají být naplánovány, a časových omezení, která musí plán dodržovat. smíšené grafy, ve kterém vrcholy (představující úkoly, které mají být provedeny) mohou být spojeny jak přesměrovanými, tak neřízenými hranami (představující časová omezení mezi úkoly). Dva typy hran představují omezení dvou různých typů:

  • Pokud jeden úkol X musí být provedeno dříve než druhý úkol y, toto omezení je představováno směrovanou hranou z X na y.
  • Pokud jsou naopak dva úkoly X a y lze provést v libovolném pořadí, ale ne současně (možná proto, že oba vyžadují použití stejného zařízení nebo jiného zdroje), toto omezení nesouběžnosti je představováno nepřímým připojením hrany X a y.

V grafu jsou od sebe odpojeny dvojice úkolů, které nemají žádné omezení v objednávání - lze je provádět v jakémkoli pořadí, nebo dokonce současně.[1][2][3]

Platný plán pro disjunktivní graf lze získat vyhledáním acyklická orientace neorientovaných hran - tj. rozhodování pro každou dvojici nesimultánních úkolů, které mají být první, bez zavedení jakéhokoli kruhové závislosti - a poté objednat výsledný směrovaný acyklický graf. Především předpokládejme, že všechny úkoly mají stejnou délku a cílem je najít plán, který minimalizuje čas, celkový čas do dokončení všech úkolů. V tomto případě lze makepan vypočítat z nejdelší cesta v orientovaném grafu, který lze najít v polynomiálním čase pro směrované acyklické grafy. Orientační fáze řešení je však mnohem obtížnější: je NP-tvrdé najít acyklickou orientaci, která minimalizuje délku nejdelší cesty. Zejména tím, že Věta Gallai – Hasse – Roy – Vitaver, pokud jsou všechny hrany zpočátku neorientované, je jejich orientace na minimalizaci nejdelší cesty ekvivalentní k nalezení optimální zbarvení grafu původního neorientovaného grafu.

Reference

  1. ^ Gröflin, H .; Klinkert, A. (2002), "Plánování se zobecněnými disjunktivními grafy: Problémy proveditelnosti", XV. Konference Evropská kapitola o kombinatorické optimalizaci (ECCO XV), 30. května - 1. června 2002, Lugano, Švýcarsko.
  2. ^ Olson, Lars E. (srpen 2003), Dotaz na disjunktivní databáze v polynomiálním čase (PDF), Diplomová práce, Univerzita Brighama Younga, Katedra výpočetní techniky.
  3. ^ Roy, S .; Sussman, B. (prosinec 1964), Les problemes d'ordonnancement avec contraintes disjonctives, Poznámka D.S. č. 9 bis, SEMA.

Další čtení

  • Balas, Egon (duben 1969), Sekvenování strojů: Disjunktivní grafy a podgrafy s omezeným stupněm„Zpráva č. 320–2971, IBM, New York Scientific Center.
  • Balas, Egon (1969), „Sekvenování strojů pomocí disjunktivních grafů: implicitní enumerační algoritmus“, Operační výzkum, 17: 941–957, doi:10.1287 / opre.17.6.941, PAN  0250770.
  • Błażewicz, Jacek; Pesch, Erwin; Sterna, Małgorzata (2000), „Disjunktivní grafická reprezentace problému plánování úlohy v obchodě“, Evropský žurnál operačního výzkumu, 127 (2): 317–331, doi:10.1016 / S0377-2217 (99) 00486-5.
  • Mason, Scott J .; Oey, Kasin (2003), „Plánování komplexních obchodů s prací pomocí disjunktních grafů: postup eliminace cyklu“, International Journal of Production Research, 41 (5): 981–994, doi:10.1080/00207540210163009