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

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

作　　者：陈小林[1] 

机构地区：[1]重庆师范大学数学与计算机科学学院,重庆400047

出　　处：《运筹与管理》2009年第3期41-45,共5页Operations Research and Management Science

基　　金：重庆市教委科技资金资助项目(KJ070802)

摘　　要：研究工件有不同的权(重要性)、但是与工件加工时间有反向"一致性"关系,并且在保证工件的一个子集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.

关 键 词：运筹学 排序 最优性 算法 

分 类 号：O223[理学—运筹学与控制论]