On scheduling multi-processor systems with algebraic objectives

Abstract

One of the well-studied models of combinatorial optimization is the scheduling problem dealing with a finite set of tasks, which have to be executed on a fixed number of machines so that a given objective is minimized. Each task requires a set of characteristic data like operating time, due date, penalty cost and technological requirements. An algebraic approach to the objective leads to a general problem which includes all classical cases of sum and bottleneck objectives known in literature. By solving an algebraic transportation problem a lower bound for the objective value can be determined. To obtain an optimal solution we employ a branch and bound procedure. Furthermore we consider the general job shop scheduling problem with algebraic objective function.

Zusammenfassung

Eines der am besten beschriebenen Modelle kombinatorischer Optimierung ist das Scheduling Problem, bei dem eine endliche Anzahl von Tätigkeiten auf einer festen Anzahl von Maschinen so ausgeführt werden muß, daß eine gegebene Zielfunktion minimiert wird. Jede Tätigkeit benötigt charakteristische Daten wie Bearbeitungszeit, Fertigsteillungstermin, Strafkosten und technologische Nachfolgebeziehungen. Ein algebraischer Ansatz für die Zielfunktion führt zu einem allgemeinen Problem, das alle in der Literatur bekannten klassischen Fälle von Summen und Maximum Zielfunktionen einschließt. Durch die Lösung eines algebraischen Transportproblems wird eine untere Schranke für den Zielfunktionswert bestimmt. Um eine Optimallösung zu erhalten, verwenden wir ein Branch and Bound Verfahren. Weiterhin betrachten wir das allgemeine Job Shop Scheduling Problem mit algebraischer Zielfunktion.