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

摘要

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