多代理排序中的若干新型问题研究

Scheduling is one of the most active branches in combinatorial optimization, among which multi-agent scheduling is a new topic attracting wide attention in recent years. As distinct from classical scheduling, in multi-agent scheduling there are multiple agents competing on the use of a common processor, each of which has a set of jobs to be processed on the same processor, and wants to optimize certain criterion depending on the completion times of its own jobs. This project will extensively investigate several new problems in multi-agent scheduling including some unexplored classical multi-agent scheduling problems, multi-agent scheduling with controllable job processing times and multi-agent scheduling with preventive maintenance. We will develop theory results and solution algorithms for the problems under consideration by analyzing the properties of feasible or optimal schedulings, analyzing the computational complexity, and designing and analyzing (pseudo-polynomial) polynomial time algorithms or approximation algorithms, and mainly focus on approximation algorithm design and worst-case analysis. The research of this project will deepen the theory research and enlarge the applying field of multi-agent scheduling, which possesses great significance in both theory and practice.

排序论是组合最优化领域中研究极为活跃的分支之一，多代理排序是近年来受到广泛重视的排序新课题。它与经典排序的主要区别在于有多个竞争代理享用共同资源来加工各自的工件，并最优化仅依赖代理自身工件完工时间的目标函数。本项目将研究多代理排序中的若干新问题，具体包括经典多代理排序中的一些未解问题，加工时间可控的多代理排序和带有预防性维护的多代理排序。通过对其可行排序或最优排序的结构性质分析，计算复杂性分析，（伪）多项式时间算法或近似算法设计与分析为所考虑的问题建立较为基本的理论体系与求解算法，核心内容是近似算法设计和最坏情况分析。本项目将对多代理排序在理论方面进行深化、在应用方面进行拓展，具有较重要的理论价值和实践意义。

排序论是组合最优化领域中研究极为活跃的分支之一，多代理排序是近年来受到广泛重视的排序新课题。它与经典排序的主要区别在于有多个竞争代理享用共同资源来加工各自的工件，并最优化仅依赖代理自身工件完工时间的目标函数。鉴于此，本项目深入研究了不相关平行机上的双代理排序问题，设计了新型的分支定价算法来精确求解这一强NP-困难问题；率先构建了若干工期可指派的多代理排序新模型，发现了复杂任务之间的耦合关系，建立了工期可指派多代理排序的理论、方法及算法体系，开辟了多代理排序新的研究问题和思路；基于准时化生产管理模式，构建了如何同时最小化多个竞争代理不同偏好和评价指标的排序模型，设计多代理排序模型的高效近似算法，攻克了多代理排序领域构建完全多项式时间近似方案的技术瓶颈；探讨了带有预防性维护和工期可指派的双代理排序问题，构建了考虑代理类型切换时间的生产配送集成优化模型，设计了结合问题结构性质的高效算法。此外，针对排序领域新涌现的其他热点问题，本项目也在加工时间可控的双目标单机排序问题、复杂不确定生产环境下的智能干扰应对方法等方面做出了一些有意义的工作。所得结果是对多代理排序问题理论研究的深化和应用领域的拓展，具有较重要的理论指导意义和实践应用价值。在本项目的资助下，共在 NRL、Omega、 EJOR、IJPR、IEEE Transactions on SMC等国际著名期刊发表(含接收) SCI论文22篇，所得结果受到国内外学者(如波兰科学院院士 J. Błażewicz、Constantin Carathéodory奖得主 P.M. Pardalos、UTD 期刊 POM 部门编辑 M.L. Pinedo 等)的广泛关注，并引发大量后续研究，目前已被SCI他引248次，2篇论文已进入ESI-TOP论文排行，1篇论文获第十八次中国物流学术年会优秀论文奖一等奖；出版英文专著1部，申请国家发明专利1项；获批国家自然科学基金面上项目1项。项目负责人连续 3 年(2016-2018年)入选爱思唯尔(Elsevier)发布的中国高被引学者榜单。