工件具有退化效应的多代理排序研究

Scheduling is one of the important areas of operations research and combinatorial optimization. Scheduling with job deteriorating effect and multi-agent scheduling are two very active research directions in the current scheduling research. Many practical instances, that jobs belong to different agents and deteriorate over time, have been found in, among others, steel production, food processing, fire fighting, resource allocation, and computer science. In the previous research work, these two categories of scheduling problems have obtained intensive results respectively. However, few studies combine these two aspects together, and so a large number of challenging issues need to be solved. This project mainly studies the solvability of the multi-agent scheduling problem with job deteriorating effect. Here “solvability” includes establishing polynomial time algorithms, constructing NP-hardness proofs, and designing approximation algorithms. On the basis of full characterization of the overall and local structural properties of the feasible schedules and optimal schedules, this project will create effective solution methods and basic theories, and make innovative research results in computational complexity analysis and design of approximation algorithms, etc.

排序是运筹学和组合最优化领域的重要研究分支之一。工件具有退化效应的排序与多代理排序是当前排序论领域十分活跃的两个研究方向。在钢铁生产、食品加工、火灾救助、资源分配以及计算机科学等领域，工件分属多个代理且随时间退化的实际例子不计其数。在已有的研究工作中，这两类排序问题各自均有较深入的研究成果。然而，将它们结合起来的研究寥寥无几，因此大量富有挑战性的问题有待解决。本项目以研究工件具有退化效应的多代理排序问题的可解性为主要内容。这里“可解性”包括建立多项式时间算法、构造NP-困难性证明以及设计近似算法。在充分刻画可行排序和最优排序的整体和局部结构性质的基础上，本项目力求建立系统有效的求解方法和基本理论，从而在计算复杂性分析和近似算法的设计等方面做出创新性的研究成果。

本项目将多代理排序和工件具有退化效应的排序结合起来，进行了广泛的研究，得到了一系列创新型的研究成果：（1）在成组加工技术环境下，研究了两个代理共同使用一台机器进行加工的排序问题。每个代理中的工件依据生产的相似性被预先分成一些工件组。对于一个代理中工件的最大费用不超过给定门槛值的限制下，最小化另一个代理中工件的最大费用问题是多项式时间可解的；对于一个代理中工件的最大延迟不超过给定门槛值的限制下，最小化另一个代理中工件的总完工时间和问题是强NP-困难的，并对代理中每个工件组中工件个数相同的情形给出多项式时间算法。（2）对于工件允许拒绝的情形，研究了两个代理协调使用一台机器进行加工的排序问题，其中各个代理的目标为最小化各自被加工工件的排序费用与被拒绝工件的拒绝费用之和。对于排序费用为时间表长、总完工时间和、最大延迟及加权误工工件数的各种组合情形给出了详尽的复杂性刻画，包括建立NP-困难性证明、设计多项式、拟多项式时间算法以及近似算法等。（3）工件分属多个不相容的工件类（代理）且在单台批容量有限制的平行批处理机进上行加工的排序问题，对目标为最小化所有工件的总加权误工工件数问题给出一个拟多项式时间算法，并综合运用多种技术设计了一个有效的完全多项式时间近似方案；对所有工件具有相同的权重以及所有工件具有相同加工时间的两种情形分别给出了快速的多项式时间算法。（4）研究工件加工时间和安装时间都是其开工时间成比例增长函数的单机排序问题。对目标为最小化最大延迟的情形给出NP-困难性证明，这同时解决了文献中的一个遗留问题，并对工件组个数固定的情形给出了多项式时间算法；对目标为总误工工件数的NP-困难问题给出了拟多项式时间算法，并对非加权和一致工期情形给出了多项式时间算法；对目标为总加权完工时间和问题给出了多项式时间算法。（5）研究具有不相容工件组和工件有到达时间且允许拒绝的单机平行批容量有界的排序问题，目标为被接受工件的最大完工时间与被拒绝工件的拒绝费用之和达到最小。利用动态规划的方法给出了一个精确算法，并设计了一个2-近似算法和一个多项式时间近似方案。