基于最小最大遗憾的变速平行机鲁棒调度问题近似算法

摘要

本文研究了总流程时间最小的变速平行机鲁棒调度问题的近似算法.其中,加工时间不确定且采用非概率的区间情景描述.首先,基于最小最大遗憾的决策准则,构建变速平行机的鲁棒调度模型;其次,指出任意调度的最大遗憾值发生在端点值情景处,并给出任意调度最大遗憾值的两个下界;然后,将以往基于中间点情景最优解的近似算法扩展到任意点情景,并推导出任意点情景解的近似比.