具有位置相关权重的工期分配排序问题研究

针对具有位置相关权重的工期分配排序问题进行了研究,其目标是在共同工期分配/松弛工期分配两种模式下,找到最优的工件加工序列以极小化工件工期与工件延误的线性加权和,其中权重是与位置相关的权重。通过证明一系列性质得到工期的计算方法,进而将所要研究的两类工期分配问题转换为与工件加工时间有关的函数。根据每个工件对应的系数来给出具体求解算法从而得到最优的工件序列,以及对应的最优共同工期/最优松弛工期。通过具体的算例验证了此算法可在多项式时间内求解。