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

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)

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  -