Complexity results for parallel machine problems with a single server (Q1860370)

The authors consider parallel machine problems with a single server. There are \(n\) jobs and \(m\) identical parallel machines. Job \(j\) (\(1\leq j\leq n\)) has to be processed without preemption on one of the machines for \(p_j\) time units. Immediately before processing, it must be loaded on the machine, which takes a set-up time of \(s_j\) time units. During such set-up the machine is also involved in the process, i.e. no other job can be processed on it. All set-ups have to be done by a single server which can handle at most one job at a time. The goal is to determine a feasible schedule which minimizes a given objective function. To specify classes of scheduling problems, the authors use the well-known \(\alpha | \beta | \gamma\) notation, which has been extended to server problems by \textit{N. Hall, C. Potts} and \textit{C. Sriskandarajah} [Discrete Appl. Math. 102, 223--243 (2000; Zbl 0972.90031)]. This extension includes the following additional information. In the \(\alpha\)-field, the entry \(S1\) indicates the presence of a single server. In the \(\beta\)-field, some information on the set-up times is indicated. Here arbitrary set-up times \(s_j\) and constant set-up times \(s_j=s\) are distinguished. All numerical data are supposed to be non-negative integers. Complexity results for parallel machine problems with a single server were obtained by N. Hall, et al. (loc. cit.) and by \textit{S. A. Kravchenko} and \textit{F. Werner} [Math. Comput. Model. 26, 1--11 (1997)]. In this paper the authors derive some new complexity results. They show that parallel machine problems with a single server, arbitrary processing times and unit set-up times are at least as difficult as the corresponding classical parallel machine problems without set-up times. On the other hand, the authors show that parallel machine problems with a single server, unit processing times, but arbitrary set-up times are at least as difficult as the corresponding single-machine problems with arbitrary processing times. These reductions lead to several NP-hardness results for problems with a single server. A number of results are also derived for the problem \(P,S1| p_j=p, s_j=s| \sum f_j\), where the objective function \(\sum f_j\) is a sum of increasing functions. The authors proved that the problems \(P2,S1| p_j=p| C_{\max}\) and \(P2,S1| p_j=p| \sum C_j\) are NP-hard, and the problem \(P,S1| s_j=1| \sum C_j\) is NP-hard in the strong sense. An \(O(n\log n)\) algorithm is presented for the problem \(P,S1| s_j=1, p_j\geq {m-2}| \sum C_j\). The authors also consider the problem \(P3,S1| s_j=1| \sum C_j\) (under the assumption that zero processing times are possible) and derive an \(O(n^7)\) algorithm for it. In the conclusion of the paper, an overview of all known to the authors complexity results for parallel machine scheduling problems with a single server and some open problems are given.