## 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