Share Email Print

Proceedings Paper

Multiprocessor scheduling problem with machine constraints
Author(s): Yong He; Zhiyi Tan
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

This paper investigates multiprocessor scheduling with machine constraints, which has many applications in the flexible manufacturing systems and in VLSI chip design. Machines have different starting times and each machine can schedule at most k jobs in a period. The objective is to minimizing the makespan. For this strogly NP-hard problem, it is important to design near-optimal approximation algorithms. It is known that Modified LPT algorithm has a worst-case ratio of 3/2-1/(2m) for kequals2 where m is the number of machines. For k>2, no good algorithm has been got in the literature. In this paper, we prove the worst-case ratio of Modified LPT is less than 2. We further present an approximation algorithm Matching and show it has a worst-case ratio 2-1/m for every k>2. By introducing parameters, we get two better worst-case ratios which show the Matching algorithm is near optimal for two special cases.

Paper Details

Date Published: 20 September 2001
PDF: 5 pages
Proc. SPIE 4555, Neural Network and Distributed Processing, (20 September 2001); doi: 10.1117/12.441674
Show Author Affiliations
Yong He, Zhejiang Univ. (China)
Zhiyi Tan, Zhejiang Univ. (China)

Published in SPIE Proceedings Vol. 4555:
Neural Network and Distributed Processing
Xubang Shen; Jianguo Liu, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?