Due to its high demand in a variety of application domains, the multiprocessor-job scheduling problem has received considerable attention recently. In this paper, we focus on the multiprocessor-job scheduling problem on 3-processor systems. We present a very simple linear time approximation algorithm based on normal scheduling of the multiprocessor-jobs, and prove that the approximation ratio of our algorithm is bounded by 1.25. A simple example shows that this is the best possible for normal scheduling on 3-processor systems. Our result improves previous results on the problem.
展开▼
