On unit task linear-nonlinear two-cluster scheduling problem

Zhichun Xiao, Wing Ning Li, John Jenq

Research output: Contribution to conferencePaperResearchpeer-review

1 Citation (Scopus)

Abstract

In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors or machines before they are scheduled. The assignment of tasks to processors is called clustering. The ordering of tasks for execution is called cluster scheduling. The set of tasks is typically modelled as a directed acyclic task graph (DAG). As a result of the clustering process, the set of tasks in each cluster either forms a total ordering, called linear, or it doesn't, called nonlinear, with respect to the DAG. It has been shown that two-cluster scheduling with one cluster being linear and the other nonlinear is strongly NP-hard. In this paper, we develop an exact algorithm to compute an optimal schedule for the above problem in O(e + α(n)n) time when tasks are restricted to unit tasks, where n is the number of nodes, e is the number of edges, and α(n) is similar to inverse Ackerman function. We also show that when both clusters are nonlinear, even when tasks are restricted to unit-tasks and task graphs are restricted to those having no path of length more than three, the problem remains NP-complete in the strong sense.

Original languageEnglish
Pages713-717
Number of pages5
DOIs
StatePublished - 1 Dec 2005
Event20th Annual ACM Symposium on Applied Computing - Santa Fe, NM, United States
Duration: 13 Mar 200517 Mar 2005

Other

Other20th Annual ACM Symposium on Applied Computing
CountryUnited States
CitySanta Fe, NM
Period13/03/0517/03/05

Fingerprint

Scheduling
Computational complexity
Processing

Keywords

  • Clustering
  • Complexity
  • Multiprocessor
  • Parallel and distributed computing
  • Scheduling

Cite this

Xiao, Z., Li, W. N., & Jenq, J. (2005). On unit task linear-nonlinear two-cluster scheduling problem. 713-717. Paper presented at 20th Annual ACM Symposium on Applied Computing, Santa Fe, NM, United States. https://doi.org/10.1145/1066677.1066839
Xiao, Zhichun ; Li, Wing Ning ; Jenq, John. / On unit task linear-nonlinear two-cluster scheduling problem. Paper presented at 20th Annual ACM Symposium on Applied Computing, Santa Fe, NM, United States.5 p.
@conference{0867ff8eaadd410daa1b4f476a0f8098,
title = "On unit task linear-nonlinear two-cluster scheduling problem",
abstract = "In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors or machines before they are scheduled. The assignment of tasks to processors is called clustering. The ordering of tasks for execution is called cluster scheduling. The set of tasks is typically modelled as a directed acyclic task graph (DAG). As a result of the clustering process, the set of tasks in each cluster either forms a total ordering, called linear, or it doesn't, called nonlinear, with respect to the DAG. It has been shown that two-cluster scheduling with one cluster being linear and the other nonlinear is strongly NP-hard. In this paper, we develop an exact algorithm to compute an optimal schedule for the above problem in O(e + α(n)n) time when tasks are restricted to unit tasks, where n is the number of nodes, e is the number of edges, and α(n) is similar to inverse Ackerman function. We also show that when both clusters are nonlinear, even when tasks are restricted to unit-tasks and task graphs are restricted to those having no path of length more than three, the problem remains NP-complete in the strong sense.",
keywords = "Clustering, Complexity, Multiprocessor, Parallel and distributed computing, Scheduling",
author = "Zhichun Xiao and Li, {Wing Ning} and John Jenq",
year = "2005",
month = "12",
day = "1",
doi = "10.1145/1066677.1066839",
language = "English",
pages = "713--717",
note = "null ; Conference date: 13-03-2005 Through 17-03-2005",

}

Xiao, Z, Li, WN & Jenq, J 2005, 'On unit task linear-nonlinear two-cluster scheduling problem' Paper presented at 20th Annual ACM Symposium on Applied Computing, Santa Fe, NM, United States, 13/03/05 - 17/03/05, pp. 713-717. https://doi.org/10.1145/1066677.1066839

On unit task linear-nonlinear two-cluster scheduling problem. / Xiao, Zhichun; Li, Wing Ning; Jenq, John.

2005. 713-717 Paper presented at 20th Annual ACM Symposium on Applied Computing, Santa Fe, NM, United States.

Research output: Contribution to conferencePaperResearchpeer-review

TY - CONF

T1 - On unit task linear-nonlinear two-cluster scheduling problem

AU - Xiao, Zhichun

AU - Li, Wing Ning

AU - Jenq, John

PY - 2005/12/1

Y1 - 2005/12/1

N2 - In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors or machines before they are scheduled. The assignment of tasks to processors is called clustering. The ordering of tasks for execution is called cluster scheduling. The set of tasks is typically modelled as a directed acyclic task graph (DAG). As a result of the clustering process, the set of tasks in each cluster either forms a total ordering, called linear, or it doesn't, called nonlinear, with respect to the DAG. It has been shown that two-cluster scheduling with one cluster being linear and the other nonlinear is strongly NP-hard. In this paper, we develop an exact algorithm to compute an optimal schedule for the above problem in O(e + α(n)n) time when tasks are restricted to unit tasks, where n is the number of nodes, e is the number of edges, and α(n) is similar to inverse Ackerman function. We also show that when both clusters are nonlinear, even when tasks are restricted to unit-tasks and task graphs are restricted to those having no path of length more than three, the problem remains NP-complete in the strong sense.

AB - In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors or machines before they are scheduled. The assignment of tasks to processors is called clustering. The ordering of tasks for execution is called cluster scheduling. The set of tasks is typically modelled as a directed acyclic task graph (DAG). As a result of the clustering process, the set of tasks in each cluster either forms a total ordering, called linear, or it doesn't, called nonlinear, with respect to the DAG. It has been shown that two-cluster scheduling with one cluster being linear and the other nonlinear is strongly NP-hard. In this paper, we develop an exact algorithm to compute an optimal schedule for the above problem in O(e + α(n)n) time when tasks are restricted to unit tasks, where n is the number of nodes, e is the number of edges, and α(n) is similar to inverse Ackerman function. We also show that when both clusters are nonlinear, even when tasks are restricted to unit-tasks and task graphs are restricted to those having no path of length more than three, the problem remains NP-complete in the strong sense.

KW - Clustering

KW - Complexity

KW - Multiprocessor

KW - Parallel and distributed computing

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=33644513045&partnerID=8YFLogxK

U2 - 10.1145/1066677.1066839

DO - 10.1145/1066677.1066839

M3 - Paper

SP - 713

EP - 717

ER -

Xiao Z, Li WN, Jenq J. On unit task linear-nonlinear two-cluster scheduling problem. 2005. Paper presented at 20th Annual ACM Symposium on Applied Computing, Santa Fe, NM, United States. https://doi.org/10.1145/1066677.1066839