带恶化效应的极小化总加权延误工件个数的单机双代理调度问题

摘要

针对钢铁企业的热轧实际生产流程，提出一类随工件加工位置呈一般线性恶化且工件正常加工时长为单位时间的单机双代理调度问题。在该问题中，热轧阶段进入冷轧厂进行冷轧的工件看作A代理商，直接销售给顾客的工件看作B代理商。A代理商的目标值为极小化最大完工时间，B代理商的目标值是极小化总加权延误工件个数，研究了在A代理商目标值不大于给定上界约束的条件下，寻找使B代理商的目标值最优的调度方案，设计了一个动态规划算法和两个时间复杂性不同的算法来求解代理商最优目标值的上下界，提出完全多项式时间近似方案，使所提的调度问题在多项式时间内可解。

关键词

双代理调度 / 最大完工时间 / 延误 / 工件 / 恶化效应 / 完全多项式时间近似方案