两台机器上具有嵌套关系处理集限制的可拒绝排序

讨论两台机器上工件具有嵌套关系处理集限制并且可拒绝的排序问题。每个工件具有各自的加工时长和拒绝费用，且可在符合其特性的机器上进行加工，或者被拒绝并支付相应的拒绝费用。可加工某工件的机器的集合，称为此工件的处理集。任意两工件的处理集具有嵌套关系，即相互包含或不相交。本文所讨论目标函数是最小化机器的时间表长与总拒绝费用的和，将给出最坏情形比为2的近似算法。