| 两个代理的单机排序问题的多项式时间算法 |
| |
| 引用本文： | 冯琪,孙晓梅,马冉,尚卫萍.两个代理的单机排序问题的多项式时间算法[J].山西大学学报(自然科学版),2012(3):448-451. |
| |
| 作者姓名： | 冯琪 孙晓梅 马冉 尚卫萍 |
| |
| 作者单位： | 郑州大学数学系;中原工程学院理学院;河南工程学院数学科学系;河南理工大学数学与信息科学学院 |
| |
| 基金项目： | 国家自然科学基金(61070229;10971201;10901144);教育部博士点基金(20111401110005);河南省教育厅自然科学研究计划项目(2010A110004);河南省自然科学研究 |
| |
| 摘 要： | 考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.
|
| 关 键 词： | 排序 多代理 多项式时间算法 |
Polynomial Time Algorithm of a Two-agent Scheduling Problem on a Single-machine |
| |
| FENG Qi,SUN Xiao-mei,MA Ran,SHANG Wei-ping.Polynomial Time Algorithm of a Two-agent Scheduling Problem on a Single-machine[J].Journal of Shanxi University (Natural Science Edition),2012(3):448-451. |
| |
| Authors: | FENG Qi SUN Xiao-mei MA Ran SHANG Wei-ping |
| |
| Institution: | 1(1.Department of Mathematics,Zhengzhou University,Zhengzhou 450001,China; 2.College of Science,Zhongyuan University of Technology,Zhengzhou 450007,China; 3.Department of Mathematical and Physical Science,Henan Institution of Engineering,Zhengzhou 451191,China; 4.College of Mathematics and Information Science,Henan Polytechnic University,Jiaozuo 454000,China) |
| |
| Abstract: | 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). |
| |
| Keywords: | scheduling multi-agent polynomial time algorithm |
| 本文献已被 CNKI 等数据库收录！ |
|
