Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0676.90029
Du, Jianzhong; Leung, Joseph Y.-T.
Complexity of scheduling parallel task systems. (English)
[J] SIAM J. Discrete Math. 2, No.4, 473-487 (1989). ISSN 0895-4801; ISSN 1095-7146/e

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.

MSC 2000:: *90B35 Scheduling theory
68Q25 Analysis of algorithms and problem complexity
68N25 Monitors and operating systems

Keywords: parallel algorithms; Parallel Task System; schedule length; nonpreemptive scheduling; strongly NP-hard; pseudo-polynomial time

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]