20 September 2001 Multiprocessor scheduling problem with machine constraints
Author Affiliations +
Proceedings Volume 4555, Neural Network and Distributed Processing; (2001) https://doi.org/10.1117/12.441674
Event: Multispectral Image Processing and Pattern Recognition, 2001, Wuhan, China
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.
© (2001) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Yong He, Yong He, Zhiyi Tan, Zhiyi Tan, } "Multiprocessor scheduling problem with machine constraints", Proc. SPIE 4555, Neural Network and Distributed Processing, (20 September 2001); doi: 10.1117/12.441674; https://doi.org/10.1117/12.441674

Back to Top