一种改进的多处理机约束混合车间调度算法

具有多处理机任务要求的多步调度问题在网络并行计算系统中十分普遍。这样的问题可以使用“具有多处理机任务约束的混合作业车间调度”(Hybrid Job-shop Scheduling with Multiprocessor Tasks,HJSMT)模型来表示,并使用“混合粒子群的优化算法”(Hybrid Particle Swarm Optimization,HPSO)求解。改进的算法在HPSO算法的基础上进行改进:原HPSO算法在求一个任务的最早开始时间时使用穷举法,每次从时间0开始向后,逐个单位时间尝试;改进后的算法运用动态规划法求解。实验结果表明,相比原始算法的改进算法,运行速度有明显的提升,原算法进行一次迭代的时间,新算法已经完成了一次实验(一次实验包含多次迭代),在保证HJSMT问题有效解决的同时提升了算法的时间效率。