具有共同窗口和可拒绝工件的排序问题

摘要

研究了同时具有可拒绝工件和共同窗口的单机排序问题，其中共同窗口的起始和结束时间都是决策变量。若工件在共同窗口期内加工完成，将不会产生额外费用，反之，则会产生提前或延误费用。对于被拒绝的工件，会有相应的拒绝费用。目标是确定哪些工件被接受或拒绝、接受加工的工作集合中的加工次序以及共同窗口的起始和结束时间，从而使得排序费用和拒绝费用的加权和最小，其中权重是位置权重。经过理论分析和算法设计，证明该问题存在时间复杂性更低的最优求解算法。

关键词

排序 / 可拒绝工件 / 单机 / 共同窗口 / 指派问题