THE K-TRACK ASSIGNMENT PROBLEM

Autor(en): BRUCKER, P
NORDMANN, L
Stichwörter: CIRCULAR ARC GRAPH; Computer Science; Computer Science, Theory & Methods; INTERVAL SCHEDULING; K-COLORING; LONGEST PATH PROBLEM
Erscheinungsdatum: 1994
Herausgeber: SPRINGER-VERLAG WIEN
Journal: COMPUTING
Volumen: 52
Ausgabe: 2
Startseite: 97
Seitenende: 122
Zusammenfassung: 
The k-track assignment problem is a scheduling problem with n jobs and k machines. Each machine j has a certain operational period (track) which starts at time a(j) and ends at time b(j). Each job i has a specific start time s(i) and a specific finish time t(i). A schedule is an assignment of certain jobs to machines such that the intervals [s(i), t(i)[ assigned to the same machine j do not overlap and fit into track [a(j), b(j)[. We are interested in a schedule which maximizes the number of assigned jobs. A O(n(k-1)k!k(k+1))-algorithm which solves this problem is presented. Furthermore it is shown that the more general problem, in which for each track only a given set of jobs can be scheduled on that track, can be solved in O(n(k)k!k(k))-time.
ISSN: 0010485X
DOI: 10.1007/BF02238071

Show full item record

Page view(s)

30
Last Week
0
Last month
0
checked on Mar 2, 2024

Google ScholarTM

Check

Altmetric