A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time

Tianyu Wang; Odile Bellenguez-Morineau

doi:10.1007/s10951-019-00602-0

A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time

Tianyu Wang^*
, Odile Bellenguez-Morineau

^*Corresponding author for this work

IMT Atlantique

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as P| p_j= 1 , in-tree | ∑ C_j with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly NP-hard.

Original language	English
Pages (from-to)	709-714
Number of pages	6
Journal	Journal of Scheduling
Volume	22
Issue number	6
DOIs	https://doi.org/10.1007/s10951-019-00602-0
State	Published - 1 Dec 2019
Externally published	Yes

Keywords

Complexity theory
In-tree
Parallel scheduling
Precedence constraints

Access to Document

10.1007/s10951-019-00602-0

Cite this

@article{5bbe13964c1a41e68cbfb0f7e8a1d0fb,

title = "A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time",

abstract = "This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as P| pj= 1 , in-tree | ∑ Cj with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly NP-hard.",

keywords = "Complexity theory, In-tree, Parallel scheduling, Precedence constraints",

author = "Tianyu Wang and Odile Bellenguez-Morineau",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2019",

month = dec,

day = "1",

doi = "10.1007/s10951-019-00602-0",

language = "英语",

volume = "22",

pages = "709--714",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer",

number = "6",

}

TY - JOUR

T1 - A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time

AU - Wang, Tianyu

AU - Bellenguez-Morineau, Odile

PY - 2019/12/1

Y1 - 2019/12/1

N2 - This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as P| pj= 1 , in-tree | ∑ Cj with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly NP-hard.

AB - This paper deals with a particular scheduling problem. We consider unit-time jobs and in-tree precedence constraints while minimizing the mean flow time. This problem is observed as P| pj= 1 , in-tree | ∑ Cj with the use of the 3-filed notation. To the best of our knowledge, its complexity is still open. Through a reduction from 3-Partition, we show that this problem is strongly NP-hard.

KW - Complexity theory

KW - In-tree

KW - Parallel scheduling

KW - Precedence constraints

UR - https://www.scopus.com/pages/publications/85061029048

U2 - 10.1007/s10951-019-00602-0

DO - 10.1007/s10951-019-00602-0

M3 - 文章

AN - SCOPUS:85061029048

SN - 1094-6136

VL - 22

SP - 709

EP - 714

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 6

ER -

A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this