多任务环境下工件带有多个时间节点的排序问题研究

In the field of combinatorial optimization, scheduling has gained much attention from both academic researchers and practical workers, because of its important value. In this project, we plan to study a new class of scheduling problems with multiple milestones under a multitasking environment, which have strong application background. The key difference between these new scheduling problems and the classical scheduling problems is that the finished amount of every job is examined at multiple milestones. For various scheduling models, we plan to analyze the time computational complexity, design algorithms and analyse their performances from theoretical and practical views on the basis of the characteristics of different problems. The idea and existing results of scheduling, mathematical programming and network optimization problems will be applied to design and analyze the algorithms and some software will also be applied for numerical experiments. Comparisons will be made between the results of these new scheduling problems and classical scheduling problems. This project opens up a new area for scheduling theory, and this is beneficial for the development of scheduling theory and combinatorial optimization. Besides, it indicates that there remain many state-of-the-art problems which can be solved by operational research models, and this is of great value for the application and development of operations research.

排序问题作为组合优化的一个分支，受到广泛关注，其众多研究成果已经被证实在理论和实践两方面都具有重要价值。本项目将首次研究多任务（Multitasking）环境下工件带有多个时间节点的排序问题，这类问题具有广泛的实际应用基础，其与经典排序问题的本质区别在于需要对每个工件在多个时间节点处考核当前的完成情况。对这类排序问题的诸多模型，本项目计划分析它们的时间计算复杂性，结合问题的特点，灵活应用排序理论、数学规划和网络优化等领域的思想和成果设计与分析算法，利用软件进行数值模拟，并将这些结果与经典排序问题的结果进行比较。本项目将会开拓排序问题全新的研究领域，不仅对推动排序理论和组合优化的研究与发展有积极的意义，而且表明存在许多具有时代特征的运筹学应用模型有待被挖掘与深入研究，这对推动运筹学的应用与发展具有非常重要的意义。

本项目致力于研究一类“需要对不同任务的拥有者公正合理地展示任务的进展”的“多任务”排序问题，根据机器环境，工件特征和目标函数的特点，我们探讨了不同的排序问题模型。本项目组开展了如下研究：（1）工件被分成若干个子工件，每个子工件有各自的加工时间和工期。只有当所有子工件都能在各自的工期前完工，该工件才能被定义为按时完工工件。我们首先证明了该问题是NP-难的，而且不存在完全多项式时间近似方案。接着，我们设计了启发式算法，利用仿真数据进行数据实验，讨论了各算法的适用性和相关性能。（2）对每个工件在其每个时间节点赋予一个惩罚函数，自变量是此工件在当前时间节点处的完成量，并且是递减的非负凸函数。目标函数是极小化所有工件在其所有时间节点处的总惩罚。我们研究了单台机器和多台平行机器的问题，并且分类研究了惩罚函数是线性函数的情形和一般凸函数的情形，提出了多项式时间算法或者分支定价算法。（3）当每个工件都可以作为子任务去干扰主任务的执行时，考虑两种工作效率提升函数作为中断函数的情形，目标是最小化最大工件完工时间、工件总完成时间、和工件完成时间的总绝对差异。我们证明了该问题对每个目标都是多项式可解的，还为一些特殊情况提供了有效的解决方案。（4）每个工件的任务可以分成两个子任务“Map”部分和“Reduce”部分。所有工件的“Map”部分由第一类机器处理，“Reduce”部分由第二类机器处理。每个工件的“Map”部分必须在“Reduce”部分之前完工，而且“Map”部分的加工时间很小，“Reduce”的加工时间较长。问题的目标函数是最小化工件最大完工时间。我们给出了近似算法，并且进行了数值模拟，用仿真数据演示不同算法在不同参数设置下的性能。我们的研究成果除了具有显著的理论意义，还可以应用到项目管理和在线服务运营等领域。