The multiprocessor job scheduling problem has received considerable attention recently. An extensive list of approximation algorithms has been developed and studied for the problem under a variety of constraints. In this paper, we show that from the viewpoint of approximability, the general multiprocessor job scheduling problem has a very rich structures such that by putting simple constraints on the number of processors in the system, we can obtain four versions of the problem, which are NP-hard with a fully polynomial time approximation scheme, strongly NP-hard with a polynomial time approximation scheme, APX-complete (thus with a constant approximation ratio in polynomial time), and with no constant approximation ratio in polynomial time, respectively.
展开▼
