最大延迟限制下两个代理的重新排序(英文)

Rescheduling for Two Agents Under a Limit on the Lateness of the Original Jobs

两个代理的重新排序问题是指,每一个代理有一个非中断加工的工件集,两个代理共用一个机器进行加工,每一个代理分别考察依赖于各自工件完工时间的目标函数.针对单机上有限错位和原始工件集最大延迟限制下,使得新工件集的最大延迟或总加工时间和最小的多代理重新排序问题,设计出几个这类问题的多项式或拟多项式时间的算法.

The rescheduling problem on two agents is considered,each with a set of nonpreemptive jobs,and the two competing to perform their respective jobs on a common processing resource.Each agent wants to minimize a certain objective function,which only depends on the completion time of its jobs.The two agents rescheduling problem for jobs on a single machine is considered to minimize maximum lateness or total completion time under a limit on the lateness of the original jobs.It is shown that the considered problems can be solved either in polynomial time or in pseudopolynomial time.