一个具有两类工件的多目标排序的多项式时间算法  

The Polynomial Time Algorithm of a Multicriteria Scheduling on Two Families of Jobs

作　　者：冯琪[1] 原晋江[2] 

机构地区：[1]中原工学院理学院,河南郑州450007 [2]郑州大学数学系,河南郑州450052

出　　处：《运筹与管理》2007年第3期52-55,共4页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(10671183)

摘　　要：本文考虑具有两个工件集的单机排序问题。第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数。问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小。本文证明该问题可在O(n1n2(n1+n2))时间内求解。We consider a single-machine scheduling problem having two families of jobs.The first family J1 has the total completion time as its objective function,and the second gamily J2 has the maximum weighted completion time as its objective function.The goal of the problem is to seek a schedule so as to minimize the total weighted objective function of two criteria.We show in this paper that the problem can be solved in O(n1n2(n1+n2))time.

关 键 词：运筹学 排序 多目标 多项式时间算法 

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