两个代理的单机排序问题的多项式时间算法  

Polynomial Time Algorithm of a Two-agent Scheduling Problem on a Single-machine

作　　者：冯琪[1,2] 孙晓梅[3] 马冉[4] 尚卫萍[1] 

机构地区：[1]郑州大学数学系,河南郑州450001 [2]中原工程学院理学院,河南郑州450007 [3]河南工程学院数学科学系,河南郑州451191 [4]河南理工大学数学与信息科学学院,河南焦作454000

出　　处：《山西大学学报（自然科学版）》2012年第3期448-451,共4页Journal of Shanxi University(Natural Science Edition)

基　　金：国家自然科学基金(61070229;10971201;10901144);教育部博士点基金(20111401110005);河南省教育厅自然科学研究计划项目(2010A110004);河南省自然科学研究

摘　　要：考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.We consider a two-agent scheduling problem on a single-machine.There are two agents A and B and each agent has respectivejob sts JA and JB,moreover,the processing times of the jobs of agent A are equal.The first agent A has the total weighted completion time as its objective function,and the second agent B has the maximum weighted completion time as its objective function.The goal of the problem is to seek for schedule such that the objective function fo agent A is minimized,given that the objective function of agent B does not exceed the given upper bound Q(Q>0).We show the problem can be solved in Q(nlogn).

关 键 词：排序 多代理 多项式时间算法 

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