The \(k\)-track assignment problem (Q1319043)

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.