Share Email Print
cover

Proceedings Paper

Multiprocessor scheduling problem with machine constraints
Author(s): Yong He; Zhiyi Tan
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

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

© SPIE. Terms of Use
Back to Top