最小化误工个数的越库调度模型与启发式算法

摘要

研究两阶段越库调度问题,目标为最小化误工个数.建立该问题的混合线性整数规划模型,在小规模情形下,利用ILOG Cplex求得精确解,并提出了基于最早交货期(EDD)的启发式算法.为评价启发式算法的计算性能,进一步构造问题的最优解下界算法,分别对小规模和中等规模问题进行数值实验,并对比启发式算法结果与精确解及下界的损失比.结果表明,所提出的启发式算法具有高效性.