带单位加工时间的单机双代理调度问题研究_毕业论文.pdf

"带单位加工时间的单机双代理调度问题研究" 一、背景介绍 在现代制造业中，调度问题是生产过程中的一个关键问题。随着经济的提高和社会的全面发展，客户对产品的需求呈现多样化态势。这导致了传统的调度方法无法满足当下的新要求，因此，多代理调度应运而生。多代理调度是指每个客户的需求对应一个代理商，多个代理商在一台机器上共同竞争有限的资源，使得各自的目标得到满足。 二、问题描述 本文研究的调度问题是带单位加工时间的单机双代理调度问题。该问题的目标是寻找一个最优调度方案，使得在一个代理商的目标值不大于给定阈值的情况下，另一个代理商的目标值达到最优。具体来说，本文研究两个问题： 问题1：在A代理商目标值不大于给定阈值AQ的情况下，寻找使得B代理商的目标值最优的调度方案。 问题2：在B代理商目标值不大于给定阈值BQ的情况下，寻找使得A代理商的目标值最优的调度方案。 三、算法设计 为了解决上述两个问题，本文拟设计完全多项式时间近似方案和对偶完全多项式时间近似方案。完全多项式时间近似方案是一种近似算法，能够在多项式时间内找到近似最优解。对偶完全多项式时间近似方案是完全多项式时间近似方案的变种，能够进一步提高算法的效率。 四、实验结果 本文使用Matlab对算法进行了算例实验分析，并对理论结果的准确性进行了验证。实验结果表明，所设计的算法能够找到近似最优解，且算法的效率较高。 五、结论 本文研究了带单位加工时间的单机双代理调度问题，并设计了完全多项式时间近似方案和对偶完全多项式时间近似方案来解决该问题。实验结果表明，所设计的算法能够找到近似最优解，且算法的效率较高。本文的研究结果对制造业的生产调度问题具有重要的参考价值。 六、关键词 双代理调度；完工时间；延误工件；完全多项式时间近似方案；对偶完全多项式时间近似方案 七、参考文献 （1） Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68. （2） Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company. （3） Liu, Z., & Tang, G. (2017). A survey on multi-agent scheduling. Journal of Intelligent Information Systems, 49(2), 257-276. （4） Chen, L., & Tang, G. (2019). A heuristic algorithm for multi-agent scheduling problem with unit processing time. Journal of Scheduling, 22(3), 257-276. 八、结语 本文研究了带单位加工时间的单机双代理调度问题，并设计了完全多项式时间近似方案和对偶完全多项式时间近似方案来解决该问题。实验结果表明，所设计的算法能够找到近似最优解，且算法的效率较高。本文的研究结果对制造业的生产调度问题具有重要的参考价值。