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

Two-agent Scheduling Problems on a Single-machine with the Total Weighted Late Work

研究同总加权误工损失有关联的两个代理间单机排序的问题.两个代理之间的排序问题中,允许工件在加工过程中中断,设总加权误工损失为第一个代理的目标函数,最大正则函数是第二个代理的目标函数.在此问题中结合EDD规则确定一个最优排序算法,使得满足第二个代理目标可行的情况下,第一个代理的目标函数最小.在上述问题最优排序规则确定的前提下,求出最优排序使得第一个代理的目标函数最小.最终给出了和总加权误工损失有关的排序问题的一个最优算法,并且证明了问题在在多项式时间内可解.

We consider two-agent scheduling problem about the total weighted late work on a single machine.The objective of the first agent is total weighted late work,while the second agent considers the number of tardy job the maximum regular function,with all jobs of both agents preemptions being allowed in the scheduling problems.The goal is to find an optimal scheduling in combination with the EDD rule in the case of model determination that minimize the objective of the first agent while keeping the second agent schedule all its job satisfy the second agent feasible.The optimal scheduling is obtained to minimize the objective function of the first agent under the condition that the optimal schedule rules above is limited.We present an optimal sorting algorithm for the total weighted late work scheduling problem and the problem is solvable in polynomial time.