ISSN:
1436-5057
Keywords:
Schedule
;
scheduling
;
sequencing
;
job
;
algorithm
;
complexity
;
precedence
;
series-parallel graph
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung n Ereignisse (oder Aufgaben), für die eine Präzedenzrelation gegeben ist, sollen unter Berücksichtigung dieser Präzedenzrelation total geordnet werden (ein Maschinen-Reihenfolgeproblem). Für jedes Ereignis sind ganzzahlige Kosten gegeben, die auch negativ sein können. Unser Ziel ist es, das Maximum der kumulativen Kosten einer solchen Reihenfolge zu minimieren, d. h. eine “kumulative kosten-optimale” Reihenfolge zu bestimmen. Wir führen den Begriff der “streng optimalen” Reihenfolgen ein und untersuchen ihre Eigenschaften. Der Nutzen dieser Reihenfolgen wird am Spezialfall “serienparalleler” Präzedenzrelationen gezeigt. In diesem Fall beschreiben wir einen Algorithmus, der eine kumulative kosten-optimale Reihenfolge mit einem Aufwand vonO (n logn) Rechenschritten bestimmt.
Notes:
Abstract Given a set ofn events (or jobs) which are constrained by a precedence relation, we want to order them into a totally ordered sequence (i. e., one machine schedule). Each event has an integer cost (which may be negative) associated with it, and our objective is to minimize the maximum cumulative cost within a schedule, i. e., to obtain a cumulative cost-optimal schedule. We introduce the concept of “strict optimality” and investigate properties of strictly optimal schedules. The usefulness of these schedules is demonstrated in the special case where the precedence relation is “series-parallel”. For this case we describe an algorithm which finds a cumulative cost-optimal schedule inO (n logn) time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02242792
Permalink