单机双代理调度问题研究：单位加工时间优化

"这篇毕业论文主要探讨了带单位加工时间的单机双代理调度问题，研究如何在满足不同代理目标的同时优化生产效率。在多代理调度的背景下，每个客户的需求由一个代理商代表，多个代理商共享同一台机器的资源。文章重点关注了双代理约束性调度问题，其中有两个代理商——A代理商和B代理商，分别追求最小化总加权完工时间和最小化总加权延误工件个数。论文提出了两个问题：在A代理商的目标值不超过阈值A_Q时找到使B代理商目标最优的调度，以及在B代理商目标值不超过阈值B_Q时找到使A代理商目标最优的调度。这两个问题都是NPC问题，因此，论文设计了完全多项式时间近似方案和对偶完全多项式时间近似方案来解决，并通过Matlab进行实例验证。" 在这篇论文中，作者深入研究了单机双代理调度问题，特别是在具有单位加工时间的环境下。问题的核心在于平衡两个代理商的利益冲突，A代理商追求的是整体的生产效率，即最小化所有工件的总加权完工时间，而B代理商关注的是减少工件的延误，即最小化总加权延误工件数量。由于这两个目标可能相互冲突，因此需要找到一个平衡点，使得在给定阈值限制下，至少一个代理能够达到其最优状态。 为了处理这个问题，论文提出了两种策略。首先，在A代理商的目标值不超过A_Q的前提下，设计了一种完全多项式时间近似方案和对应的对偶解决方案，以优化B代理商的目标。接着，针对B代理商的目标值不超过B_Q的情况，设计了一个完全多项式时间近似方案来最大化A代理商的效益。这些算法的创新之处在于它们能够在复杂度上保持可接受，同时尽可能地接近最优解。 最后，通过Matlab软件进行了数值实验，以检验所提出的算法在实际应用中的表现和理论结果的准确性。实验结果不仅验证了算法的有效性，也为解决类似的实际调度问题提供了有价值的参考。这篇论文对于理解如何在多代理环境下进行有效的资源分配和调度策略设计具有重要的理论和实践意义。