Plánování na jednom stroji - Single-machine scheduling

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Plánování na jednom stroji“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Plánování na jednom stroji nebo plánování jednoho zdroje je proces přiřazení skupiny úkolů jednomu počítači nebo prostředku. Úkoly jsou uspořádány tak, aby bylo možné optimalizovat jedno nebo více měr výkonu.

Měření výkonu

Míry výkonu úkolů v problému plánování jednoho stroje zahrnují:

• Nedochvilnost – ${displaystyle max (0, příjem; datum splatnosti; datum)}$
• Časnost – ${displaystyle max (0, splatnost; datum-příjem; datum)}$
• Opoždění – ${displaystyle receive; date-due; date}$
• Doba toku – ${displaystyle end; date-start; date}$

Techniky řešení

Při řešení problémů s plánováním na jednom stroji bylo použito mnoho technik řešení. Některé z nich jsou uvedeny níže.

Heuristika

• Nejkratší doba zpracování (SPT)

Plán SPT je optimální, pokud je cílem minimalizovat průměrnou dobu toku.

SPT-order je objednávka založená na době zpracování. Posloupnost zbývajících úloh seřazených na základě neklesající doby zpracování.

• Nejbližší termín splatnosti (EDD)

Plán EDD je optimální, pokud je cílem minimalizovat maximální zpoždění.

EDD objednávka je objednávka založená na termínu splatnosti. Posloupnost zbývajících úloh seřazených podle neklesajícího data splatnosti.

Poznámka: „Latence“ je jakákoli odchylka od data splatnosti. Pozitivní opožděnost je „pozdnost“, negativní opožděnost je „časnost“

• Hodgsonův algoritmus

Hodgsonův algoritmus poskytuje optimální řešení, pokud je cílem minimalizovat počet úloh s časovou prodlevou větší než nula.

Výpočetní

• Genetické algoritmy
• Neuronové sítě
• Simulované žíhání
• Optimalizace kolonií mravenců
• Tabu vyhledávání

Reference