Scheduling-Aufgaben (II)

die meisten dieser Aufgaben sind schwer,

• genauer: NP-vollständig.
• d. h. (wahrscheinlich) exponentielle Laufzeit

man hätte gern Näherungsverfahren

• in Polynomialzeit
• mit beschränktem Fehler

Bsp. Bin-Packing: First Fit, First Fit Decreasing.