Multiprocessor scheduling problem with machine constraints

Yong He; Zhiyi Tan

doi:10.1117/12.441674

20 September 2001 Multiprocessor scheduling problem with machine constraints

Yong He, Zhiyi Tan

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

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.

Citation Download Citation

Yong He and Zhiyi Tan "Multiprocessor scheduling problem with machine constraints", Proc. SPIE 4555, Neural Network and Distributed Processing, (20 September 2001); https://doi.org/10.1117/12.441674

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available