Proceedings of the 2017 2nd International Conference on Materials Science, Machinery and Energy Engineering (MSMEE 2017)

A Polynomially Solvable Case of Scheduling Multiprocessor Tasks in a Multi-Machine Environment

Authors
Xiao Xin, Min Mou, Guohua Mu
Corresponding Author
Xiao Xin
Available Online May 2017.
DOI
10.2991/msmee-17.2017.317How to use a DOI?
Keywords
Parallel Processing, Scheduling, Multiprocessor tasks, Makespan, Polynomially solvable case.
Abstract

The problem of scheduling multiprocessor tasks in a multi-machine environment is considered. Each machine contains a number of identical processors. Each task requires a number of processors on a single machine for its processing. The objective is to minimize the overall task completion time, i.e. the makespan. The general problem has been known to be strongly NP-hard. A linear time optimal algorithm is presented for a special case of the problem where all the tasks have unit processing times and each task requires one or k (k is part of the input) processors. The small computational effort of the algorithm is valuable in some practical applications.

Copyright
© 2017, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2017 2nd International Conference on Materials Science, Machinery and Energy Engineering (MSMEE 2017)
Series
Advances in Engineering Research
Publication Date
May 2017
ISBN
978-94-6252-346-3
ISSN
2352-5401
DOI
10.2991/msmee-17.2017.317How to use a DOI?
Copyright
© 2017, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Xiao Xin
AU  - Min Mou
AU  - Guohua Mu
PY  - 2017/05
DA  - 2017/05
TI  - A Polynomially Solvable Case of Scheduling Multiprocessor Tasks in a Multi-Machine Environment
BT  - Proceedings of the 2017 2nd International Conference on Materials Science, Machinery and Energy Engineering (MSMEE 2017)
PB  - Atlantis Press
SP  - 1746
EP  - 1749
SN  - 2352-5401
UR  - https://doi.org/10.2991/msmee-17.2017.317
DO  - 10.2991/msmee-17.2017.317
ID  - Xin2017/05
ER  -