English

运筹学学报 >

2015 , Vol. 19 >Issue 2: 54 - 60

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.02.006

运筹学

有关单机两代理排序问题的两个结果

展开
  • 1. 江西财经大学信息管理学院, 南昌 330013

收稿日期: 2014-07-07

  网络出版日期: 2015-06-15

基金资助

国家自然科学专项基金(No. 11426120), 江西省自然科学基金(No. 20142BAB211017), 江西财经大学校级课题(No. 06162015)

收起

Two results for single-machine two-agent scheduling problems

Expand
  • 1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China

Received date: 2014-07-07

  Online published: 2015-06-15

Fold

摘要

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.

关键词： 两代理排序; 算法复杂度; 最优算法

本文引用格式

万龙 . 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015 , 19(2) : 54 -60 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.006

Abstract

The paper considers two two-agent scheduling problems on a single machine. For the first two-agent scheduling problem, the objective of agent A is to minimize the total weighted completion time of all jobs of agent A while the objective of agent B is to minimize the maximum cost of the jobs of agent B. For the second two-agent scheduling problem, the objective of agent A is to minimize the total completion time of all jobs of agent A while the objective of agent B is to minimize the makespan which is defined as the maximum completion time of all the jobs of agent B. In this paper, we prove that the first problem is NP-hard in the strong sense which improves the current complexity result and design a dynamic programming other than the previous known algorithm for the second problem.

Key words： two-agent scheduling; algorithm complexity; optimal algorithm

参考文献

Baker K R, Smith J C. A multiple criterion model for machine scheduling [J]. Journal of Scheduling}, 2003, 6: 7-16.


Agnetis A, Mirchandani P B, Pacciarelli D, et al. Scheduling problems with two competing agents [J]. Operations Research, 2004, 52: 229-242.

Yuan J J, Shang W P, Feng Q. A note on the scheduling with two families of jobs [J]. Journal of Scheduling, 2005, 8: 537-542.

Cheng T C E, Ng  C T, Yuan J J. Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs [J]. Theoretical Computer Science, 2006, 362: 273-281.

Cheng T C E, Ng C T, Yuan J J. Multi-agent scheduling on a single machine with max-form criteria [J]. European Journal of Operational Research, 2008,
188: 603-609.

Li S S, Yuan J J. Unbounded parallel-batching scheduling with two competitive agents [J]. Journal of Scheduling, 2012, 15: 629-640.

Fan B Q, Cheng T C E, Li S S, et al. Bounded parallel-batching scheduling with two competing agents [J]. Journal of Scheduling, 2013, 16: 261-271.

Wan G H, Vakati S R, Leung J Y T, et al. Scheduling two agents with controllable processing times [J]. European Journal of Operational Research, 2010, 205: 528-539.
Yin Y Q, Cheng S R, Wu C C. Scheduling problems with two agents and linear non-increasing deterioration to minimize earliness penalties [J]. Information Sciences, 2012, 189: 282-292.
Leung J Y T, Pinedo M, Wan G H. Competitive two agent scheduling and its applications [J]. Operations Research, 2010, 58: 458-469.
Yuan J J, Ng C T, Cheng T C E. Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness [J]. Journal of Scheduling, 2014, DOI: 10.1007/s10951-013-0360-y.

Wan L, Yuan J J, Geng Z C. A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints [J]. Journal of Scheduling, 2014, DOI: 10.1007/s10951-014-0368-y.

Graham R L, Lawler E L, Lenstra J K, et al. Optimization and heuristic in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

Agnetis A, de Pascale G, Pacciarelli D. A Lagrangian approach to single-machine scheduling problems with two competing agents [J]. Journal of Scheduling, 2009, 12: 401-415.

Garey M, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Complete-\\ness [M]. New York: W H Freeman and Company, 1979.

 
Options
文章导航

/

〈 〉