CAJ | 학술논문

为合理利用多处理器资源，对任务调度算法进行研究，针对现有任务调度算法在任务规模较大的情况下全局寻优能力方面的不足，提出基于禁忌搜索的多处理器任务调度算法。对任务图不设任何约束条件，利用基于任务复制的T DS算法产生高质量的初始调度以降低算法复杂度，利用禁忌搜索算法全局寻优得到最优调度。实验结果表明，该算法可以有效降低任务调度长度，减少所需处理器数目。
위합리이용다처리기자원，대임무조도산법진행연구，침대현유임무조도산법재임무규모교대적정황하전국심우능력방면적불족，제출기우금기수색적다처리기임무조도산법。대임무도불설임하약속조건，이용기우임무복제적T DS산법산생고질량적초시조도이강저산법복잡도，이용금기수색산법전국심우득도최우조도。실험결과표명，해산법가이유효강저임무조도장도，감소소수처리기수목。
To make rational use of multiprocessor resources ,task scheduling algorithms were studied .Aiming at the shortage of existing algorithms in solving large‐scale problems ,a multiprocessor scheduling algorithm based on the tabu search was pro‐posed .Firstly ,the task duplication based scheduling algorithm (TDS) was used to generate an initial schedule to reduce the time complexity .Then ,the tabu search was used to find the optimal schedule .The proposed algorithm can generate a schedule with the minimal makespan and the number of processors needed is reduced simultaneously without any constraints on task graphs . Finally ,the experimental results demonstrate the validity of the algorithm .