Du, Jianzhong; Leung, Joseph Y.-T. Complexity of scheduling parallel task systems. (English) Zbl 0676.90029 SIAM J. Discrete Math. 2, No. 4, 473-487 (1989). Summary: One of of the assumptions made in classical scheduling theory is that a task is always executed by one processor at a time. With the advances in parallel algorithms, this assumption may not be valid for future task systems. In this paper, a new model of task systems is studied, the so- called Parallel Task System, in which a task can be executed by one or more processors at the same time. The complexity of scheduling Parallel Task Systems to minimize the schedule length is examined. For nonpreemptive scheduling, it is shown that the problem is strongly NP- hard even for two processors when the precedence constraints consist of a set of chains. For independent tasks, the problem is strongly NP-hard for five processors, but solvable in pseudo-polynomial time for two and three processors. For preemptive scheduling, it is shown that the problem is strongly NP-hard for arbitrary number of processors for a set of independent tasks. Furthermore, it is shown that it is NP-hard, but solvable in pseudo-polynomial time, for a fixed number of processors. Cited in 49 Documents MSC: 90B35 Deterministic scheduling theory in operations research 68Q25 Analysis of algorithms and problem complexity 68N25 Theory of operating systems Keywords:parallel algorithms; Parallel Task System; schedule length; nonpreemptive scheduling; strongly NP-hard; pseudo-polynomial time PDFBibTeX XMLCite \textit{J. Du} and \textit{J. Y. T. Leung}, SIAM J. Discrete Math. 2, No. 4, 473--487 (1989; Zbl 0676.90029) Full Text: DOI