Brucker, Peter; Knust, Sigrid; Roper, Duncan; Zinder, Yakov Scheduling UET task systems with concurrency on two parallel identical processors. (English) Zbl 1023.90023 Math. Methods Oper. Res. 52, No. 3, 369-387 (2000). Summary: Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of {C. Y. Lee} and X. Cai [Naveal Res. Logist. (to appear)]. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family. Cited in 9 Documents MSC: 90B35 Deterministic scheduling theory in operations research 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68W25 Approximation algorithms 90C59 Approximation methods and heuristics in mathematical programming Keywords:scheduling; unit execution time tasks; concurrency; identical parallel processors; complexity; approximation algorithm; NP-hardners PDFBibTeX XMLCite \textit{P. Brucker} et al., Math. Methods Oper. Res. 52, No. 3, 369--387 (2000; Zbl 1023.90023) Full Text: DOI