两代理单机排序问题：最小化误工与加权完工时间

"这篇论文研究了在两代理单机排序问题中的优化策略，重点关注如何在误工工件不超过特定数量的前提下最小化总误工或总加权完工时间。论文提出了动态规划方法来解决这两个问题，并给出了相应的拟多项式时间算法。" 在多代理排序问题中，通常涉及两个或更多代理，每个代理都有自己的目标函数。这类问题的目的是找到一个排序方案，使得所有代理的目标函数都能达到最优或满意状态。早期的研究主要集中在两个代理的排序问题上，目标函数可能包括最大值、误工工件个数以及总加权完工时间等。 本论文特别关注的是在单机环境中，当误工工件不超过给定限制时，如何实现总误工最小化和加权完工时间之和最小化。作者首先定义了两个具体问题：一是寻找在误工工件不超过设定值的条件下，如何安排工作以最小化总误工；二是当代理A的工件加工时间和权重满足反一致关系时，同样在误工工件不超过设定值的情况下，如何最小化总加权完工时间。 为了解决这些问题，论文采用了动态规划的方法。动态规划是一种有效的优化工具，它通过构建决策过程的子问题来逐步求解整个问题。在本文的背景下，动态规划可能涉及到构建一个状态空间，其中每个状态代表了当前处理的工作集合以及已产生的误工情况。通过计算转移函数和边界条件，可以找到达到最优解的路径。 此外，论文还提供了拟多项式时间算法，这意味着尽管问题的规模可能会随着输入的增加而指数级增长，但算法的运行时间仍然能保持在一个相对较低的阶，从而在实际应用中是可行的。 文中提及了其他学者对多代理排序问题的研究，如不同目标函数的设置、工件的序约束、到达时间的影响以及开机时间相关的非增线性退化问题。这些研究都为理解排序问题的复杂性和寻找有效解决方案提供了背景和基础。 这篇论文对两代理单机排序问题进行了深入研究，提出了新的优化目标和算法，为解决实际生产调度中的此类问题提供了理论支持和技术手段。通过动态规划和拟多项式时间算法的结合，论文为减少误工并优化总完工时间提供了理论框架，这对于工业生产计划和调度领域具有重要的实践意义。