运筹学学报

• 运筹学 • 上一篇    下一篇

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

马露 张新功1,*   

  1. 1. 重庆师范大学数学科学学院, 重庆 400047
  • 收稿日期:2015-11-12 出版日期:2017-03-15 发布日期:2017-03-15
  • 通讯作者: 张新功 zxg7980@163.com
  • 基金资助:

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

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

MA Lu1   ZHANG Xingong1,*   

  1. 1. College of Mathematics Science, Chongqing Normal University, Chongqing 400047, China
  • Received:2015-11-12 Online:2017-03-15 Published:2017-03-15

摘要:

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

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

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