安装时间具有退化效应的MapReduce模型下的平行机调度

考虑了平行机环境下安装时间具有退化效应且加工时间具有分步恶化效应的MapReduce模型调度优化问题。在MapReduce模型中,每个工件包含Map和Reduce两道工序。其中,Map工序可以分割成若干个子任务并在多台平行机上同时加工,而Reduce工序只有在该工件Map工序的所有子任务完成后才能启动加工,而且只能在一台机器上连续加工。研究Reduce工序的启动安装时间具有线性恶化效应、两个工序的加工时间具有分步恶化效应的平行机调度问题,构建了以最小化最大完成时间为优化目标的混合整数规划模型。给出了问题解的一个下界;同时,设计了采用单纯形差分扰动机制的改进灰狼算法以及贪婪算法进行模型求解。最后,利用数值仿真实验,将灰狼优化算法、贪婪算法、遗传算法的解与问题的下界进行对比,验证了模型与所设计算法的有效性。