The \(k\)-track assignment problem (Q1319043): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Scheduling jobs with fixed start and end times / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Complexity of Coloring Circular Arcs and Chords / rank | |||
Normal rank |
Revision as of 14:28, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The \(k\)-track assignment problem |
scientific article |
Statements
The \(k\)-track assignment problem (English)
0 references
12 April 1994
0 references
An interval scheduling problem is considered in which there are \(n\) jobs, each with specified start and finish times. The jobs are to be scheduled on \(k\) machines, where each machine can process at most one job at a time and each has a given interval of availability during which it may process jobs. The objective is to maximize the number of jobs that are scheduled. Network formulations of the problem are proposed in which an optimal schedule is obtained by finding a longest path. For a constrained version of the problem in which each machine can only process jobs from a given subset, the network has at most \(O(n^ k)\) vertices, and a longest path is found in \(O(n^ k k! k^ k)\) time. The complexity is improved for the unconstrained problem in which the jobs that a machine can process are defined only by the relevant intervals: the number of vertices is at most \(O(k^ 2 n^{k- 1})\), and \(O(n^{k- 1} k! k^{k+ 1})\) time is required to find a longest path. Computational results with up to 100 jobs show that the proposed algorithm requires less computation time than an algorithm of \textit{E. M. Arkin} and \textit{E. B. Silverberg} [Discrete Appl. Math. 18, 1-8 (1987; Zbl 0636.90042)] for problems with two and three machines, and storage requirements for the proposed algorithm are smaller.
0 references
parallel machines
0 references
interval scheduling
0 references
longest path
0 references