非同起点加工的多机调度合成算法

针对调度h个独立任务到初始时刻并非都空闲的m台机器上加工，使得机器最长加工时间（makespan）最短的问题，改进MLPT算法以减少运行时间，改进MULTIFIT算法以减少迭代次数，提出以改进的MLPT算法结果为改进的MULTIFIT算法的初始上界的合成算法－CMM，从理论上对MLPT，MULTIFIT和CMM算法的时间复杂度和调度结果进行了分析和比较，实验结果表明：改进的MULTIFIT经MULTIFIT的平均迭代次数少；CMM在平均迭代次数方面甚至比改进的MULTIFIT还少得多且调度结果不次于MULTIFIT和MLPT的优者。

A Combined Algorithm for Nonsimultaneous Multiprocessor Scheduling

The nonsimultaneous multiprocessor scheduling problem (NMSP for short) is a generalization of the classical simultaneous multiprocessor scheduling problem (SMSP for short), where all jobs and machines are available at time zero. NMSP concerns the nonpreemptive assignment of n independent 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 number of iterations of MMULTIFIT is smaller than that of MULTIFIT, the average number of iterations of CMM is rather smaller 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 processor scheduling in computer systems, etc..