摘要
针对调度 n个独立任务到初始时刻并非都空闲的 m台机器上加工 ,使得机器最长加工时间 (m akespan)最短的问题 ,改进 ML PT算法以减少运行时间 ,改进 MU L TIFIT算法以减少迭代次数 ,提出以改进的 ML PT算法结果为改进的 MU L TIFIT算法的初始上界的合成算法—— CMM,从理论上对 ML PT,MUL TIFIT和 CMM等算法的时间复杂度和调度结果进行了分析和比较 .实验结果表明 :改进的 MUL TIFIT比 MUL TIFIT的平均迭代次数少 ;CMM在平均迭代次数方面甚至比改进的 MUL TIFIT还少得多且调度结果不次于 MUL TIFIT和 ML PT的优者 .
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..
出处
《计算机学报》
EI
CSCD
北大核心
2002年第8期817-822,共6页
Chinese Journal of Computers
基金
国家"八六三"高技术研究发展计划 CIMS主题项目 ( 86 3-5 11-944-0 0 1)资助
关键词
多机调度合成算法
合成算法
时间复杂度
算法分析
nonsimultaneous multiprocessor scheduling, combined algorithm, MULTIFIT, identical processors
