一个具有退化的两个代理的排序问题  

A Two-agent Scheduling Problem with Deterioration

作　　者：冯琪[1,2] 孙晓梅[3] 刘瑞芳[1] 

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

出　　处：《数学的实践与认识》2012年第5期133-136,共4页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10971201;61070229);河南省教育厅自然科学研究计划项目(2010A110004)河南省教育厅自然科学基金(2011A110021)

摘　　要：考虑两个代理的带有退化的单机排序问题.第一个代理J以完工时间和为目标函数,第二个代理J以最大延迟为目标函数,并且两个代理的加工时间是按时间退化的,所谓按时间退化就是每个工件的加工时间是其开始加工时间的函数.问题的目标是寻找一种排序,使得两个代理的目标函数之和达到最小.证明该问题可在O(n_1n_2(n_1+n_2))时间内求解.We consider a two-agent scheduling problem on a single-machine with deterio- ration. The first agent j（1） has the total completion time as its objective function, and the second agent j（2） has the maximum lateness as its objective function. Moreover, the process- ing time of each job in each agent is deteriorating by time, i.e., the processing time of each job is the function of its starting time. The goal of the problem is to seek for a schedule such that the sum of the two objective function of the two agents is minimized. We show in this paper that the problem can be solved in O（nln2（nl ＋ n2）） time.

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

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