Combined algorithm for nonsimultaneous multiprocessor scheduling

The nonsimultaneous multiprocessor scheduling problem (NMSP) is a generalization of the classical simultaneous multiprocessor scheduling problem (SMSP), where all jobs and machines are available at time zero. NMSP concerns the nonpreemptive assignment of nindependent jobs on m parallel machines in order to minimize the makespan, in which all jobs are available at time zero but some machines may not available at time zero. MLPT and MULTIFIT are two typical algorithms for NMSP. In this paper, both MLPT and MULTIFIT are modified. MMLPT (Modified MLPT) needs less running time than MLPT and MMULTIFIT (Modified MULTIFIT) needs fewer iterations than MULTIFIT. CMM is presented which combines MMLPT with MMULTIFIT in such a way that the initial upper bound of MMULTIFIT starts with the makespan of MMLPT. The complexities and scheduling outcomes of MLPT, MULTIFIT and CMM are analyzed and compared theoretically. Experimental results show that the average iterations of MMULTIFIT is fewer than that of MULTIFIT, the average number of iterations of CMM is rather fewer even than that of MMULTIFIT and the performance of CMM is not worse than the better of MMULTIFIT and MMLPT. CMM can be used to such problems as the work floor jobs scheduling in enterprises, the processors scheduling in computer systems, etc.