工件可自由下线的平行批 ND-双代理排序研究

ND-two-agent scheduling is a new model of two-agent scheduling, which is characterized by allowing the job sets of two agents to intersect. Therefore, ND-two-agent scheduling is a generalization of the competitive two-agent scheduling and the classical two-criteria scheduling. Parallel-batch scheduling is an important research topic in scheduling theory, which is characterized by allowing multiple jobs to be processed in the same batch. In parallel-batch scheduling with drop-line jobs, all jobs contained in the same batch have a common starting time, but the completion time of each job is equal to the sum of the starting time of the batch containing the job and the processing time of the job. This model is widely applied in logistics and supply chain management, information network optimization and so on, but the model has not been fully studied. This project studies the ND-two-agent scheduling problems on a parallel-batch machine with drop-line jobs in both bounded setting and unbounded setting with respect to the batch capacity. Aiming at the scheduling criteria, such as, makespan, maximum lateness, Max-form scheduling cost, (weighted) total completion time, (weighted) the number of tardy jobs, (weighted) total late work and Sum-form scheduling cost, we will obtain systematic and complete research results in the aspects of computational complexity analysis and algorithm designing.

ND-双代理是一类新的双代理排序模型，其特点是允许两个代理的工件集相交。因此，ND-双代理排序是竞争双代理排序和经典双指标排序的推广。平行批排序是排序论的一个重要研究课题，其特点是允许多个工件在同一批中进行加工。在工件可自由下线的平行批排序模型中，同一个批的工件具有相同的开工时间，但每一个工件的完工时间等于该工件所在批的开工时间与其自身的加工时间之和。该模型广泛地应用于物流与供应链管理以及信息网络优化等领域，但是尚未被充分的进行研究。本项目在批容量有界和无界两种情形下研究工件可自由下线的平行批ND-双代理排序问题。针对时间表长、最大延迟、Max-型排序费用、（加权）完工时间总和、（加权）误工工件数、（加权）误工量总和以及Sum-型排序费用等排序指标，在计算复杂性分析和算法设计方面得到系统完整的研究成果。

ND-双代理是一种允许两个代理的工件集相交的双代理排序模型。平行批排序是排序论的一个重要研究课题，其特点是允许多个工件在同一批中进行加工。在工件可自由下线的平行批排序模型中，工件的完工时间等于该工件所在批的开工时间与其自身的加工时间之和。本项目将这两种排序模型结合起来进行研究，具有丰富的研究内涵。本项目代表性研究成果如下：（1）对单机上有两个竞争代理最小化A-工件的总排序费用和B-工件的最大排序费用的Pareto最优化排序问题，其中每个工件都有一个位置期限和一个截止工期，A-工件有相同的加工时间，B-工件有加工顺序的约束，给出了多项式时间算法。（2）对单台无界平行批机器上在IG假设下最小化A-工件的最大完工时间和B-工件的最大排序费用的ND-双代理的Pareto最优化排序问题，给出了多项式时间算法。（3）对单台无界平行批机器上有批工件或自由下线工件最小化最大完工时间和最大排序费用的双指标Pareto最优化排序问题，其中工件有一致的到达时间和加工时间，分别给出了多项式时间算法。（4）证明了GDD或ADD假设下最小化总加权误工量的单机排序问题的一元NP-困难性，解决了文献中长期悬而未决的问题。