探讨了两台平行批处理机的调度决策问题,着重考虑了订单具有不同加工类型、同一批次只能加工相同类型的订单以及机器批容量有限的调度情形。针对订单实时到达且需要立即决策是否接受的实际情景,运用在线理论构建了平行机批调度在线模型。证明了该问题的竞争比下界为■,其中B和w分别表示批容量和单个订单的最大完工收益。进而设计给出了收益阈值算法PT并证明其对于订单具有紧交货期限的情形竞争比为■;对于非紧交货期限的情形,证明了修正的PT算法具有竞争比为■。
科研之友
微信
新浪微博
Facebook
分享链接
