English

运筹学学报 >

2017 , Vol. 21 >Issue 1: 13 - 22

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

运筹学

关于总误工损失的两个代理单机排序问题

展开
  • 1. 重庆师范大学数学科学学院, 重庆 400047

收稿日期: 2015-11-12

  网络出版日期: 2017-03-15

基金资助

国家自然科学基金(Nos. 11401065, 11571321)，重庆市教委项目(No. KJ1600326), 重庆市自然科学基金(No. cstc2014jcyjA00003)

收起

Two-agent scheduling problem about total late  work on a single machine

Expand
  • 1. College of Mathematics Science, Chongqing Normal University, Chongqing 400047, China

Received date: 2015-11-12

  Online published: 2017-03-15

Fold

摘要

研究了与总误工损失相关的两个代理的单机排序问题. 第一个代理以工件的总误工损失为目标函数, 第二个代理以工件的总完工时间或总误工工件数为目标函数. 目标是寻找一个排序, 使得在第二个代理的目标函数不超过给定的上界的条件下, 第一个代理的目标函数值最小. 对这两个与总误工损失相关的两个代理的单机排序问题, 分别给出它们的拟多项式时间的动态规划算法.

关键词： 排序; 两个代理; 总误工损失; 动态规划算法

本文引用格式

马露, 张新功 . 关于总误工损失的两个代理单机排序问题[J]. 运筹学学报, 2017 , 21(1) : 13 -22 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.01.002

Abstract

We consider two-agent scheduling problem about total late work on a single machine. The first agent has total late work as its objective function, while the second agent considers either the total complete time or the number of tardy jobs as its objective function. The goal is to find a schedule that minimize the objective of the first agent while keeping the objective of the second agent cannot exceed a giving upper bound. We present a pseudo-polynomial time algorithm for these two scheduling problem, respectively.

Key words： scheduling; two-agent; total late work; polynomial programming algorithm

参考文献

[1] Agnetis A, Mirchandani P B, Pacciarelli D, et al. Scheduling problems with two competing agents [J]. Operations Research, 2004, 52(2): 229-242.
[2] Joseph Y T L, Pinedo M, Wan G H. Competitive two-agent scheduling and its applications [J]. Operations Research, 2010, 52(8): 458-469.
[3] Perez-Gonzalez P, Framinan J M. A common framework and taxonomy for multi-criteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems [J]. European Journal of Operational Research, 2014, 235(1): 1-16.
[4] 万龙. 有关单机两代理排序问题的两个结果 [J]. 运筹学学报, 2015, 19(2): 54-60.
[5] Potts C N, Van Wassenhove L N. Single machine scheduling to minimize total late work [J]. Operations Research, 1992, 40(3): 586-595.
[6] 戴秦, 郑兴山, 张新功, 等. 总迟后相关的两个工况代理的单机排序问题 [J]. 工业 工程与管理, 2014, 19(6): 78-88.
[7] Sterna M. A survey of scheduling problem with late work criteria [J]. Omega, 2011, 39: 120-129.
[8] Graham P L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic machine scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5(1): 287-326.
[9] Peter B. Scheduling Algorithms [M].  Springer-Verlag Berlin Heidelberg New work, 2006.
[10] Ng C T, Cheng T C E, Yuan J J. A note on the complexity of two-agent scheduling on a single machine [J]. Journal of Combinatorial Optimization, 2006, 12: 387-394.
Options
文章导航

/

〈 〉