带权的误工排序问题的最优算法

The Optimal Algorithm to Minimize the Weighted Number of Late Jobs both for Reverse Agreeability of Processing Times with Weights When a Subset of Jobs Must Be on Time

研究工件有不同的权(重要性)、但是与工件加工时间有反向"一致性"关系,并且在保证工件的一个子集T中的工件必须不误工的前提下,使得带权的误工工件的个数(误工造成损失的费用)为最少的排序问题1|T,(pi≤pj)(wi≥wj)|∑wjUj;提出该问题的最优算法,证明提出的算法得到的排序是最优排序,而且证明这个最优排序在所有最优排序中不误工工件总的加工时间为最小。

：In this paper, we address the scheduling problem I｜T,（n≤P1）→（Wi≥wj）｜∑wjUjto minimize the number of late jobs both for reverse agreeability of processing times with weights when a subset T of jobs must be on time. We propose an optimal algorithm for the problem, and prove the algorithm will get the optimal solution, and prove the solution finding by the algorithm has the shortest total processing time among all optimality solutions.