这篇文档属于类型a，即报告了一项原创性研究。以下是针对该研究的学术报告：
作者及机构
本研究由Hehuan Shi、Lin Chen（通讯作者）、Ming Lin（均来自中山大学计算机科学与工程学院）以及Raphael C.-W. Phan（马来西亚莫纳什大学信息技术学院）合作完成，发表于2023年8月的第52届国际并行处理会议（ICPP 2023），论文标题为《Scheduling Dependent Batching Tasks》。
学术背景
研究领域与动机
该研究属于任务调度（task scheduling）领域，聚焦于依赖批处理任务（dependent batching tasks）的调度问题。传统调度理论通常假设任务互斥执行（即资源同一时间仅处理单一任务），但实际场景中（如无线通信网络的多播传输、数据库的并发读写），部分任务可批量执行（batching），而任务间可能存在依赖关系（dependency）。现有研究多针对独立任务或互斥任务，缺乏对依赖关系与批处理共存场景的系统性研究。
研究目标
- 提出一个通用模型，描述任务依赖（DAG结构）与批处理分组的联合约束；
- 设计离线（offline）与在线（online）调度算法，最大化系统收益（reward）；
- 理论证明问题的计算复杂性，并提出具有确定性性能保证的近似算法。
研究流程与方法
1. 问题建模
- 任务定义：每个任务$i$由五元组$(a_i, d_i, l_i, w_i, b_i)$描述，分别为释放时间、截止时间、执行时长、收益和所属批处理组。
- 依赖约束：任务依赖关系构成有向无环图（DAG），本研究聚焦树状依赖（tree/forest topology）。
- 冲突约束：不同批处理组的任务执行时间不可重叠。
2. 离线调度算法设计
- 任务图（Task Graph）构建：
- 顶点：为每个任务$i$的所有可行执行时间窗口$[a_i + m, a_i + li + m - 1]$生成顶点$v{i,m}$，权重为$w_i$。
- 边：分三类——（1）同一任务的顶点间边（保证单次执行）；（2）不同批处理组且时间重叠的顶点间边（冲突约束）；（3）依赖任务的顶点间边（父任务需先完成）。
- 转化为MWRIS问题：将调度问题映射为最大权重正则独立集（Maximum Weighted Regular Independent Set, MWRIS）问题，即选择无冲突且满足依赖关系的顶点集以最大化总权重。
- LP松弛与舍入算法：
- 对整数线性规划（ILP）松弛求解；
- 构造辅助图并通过着色算法（coloring algorithm）将分数解舍入为整数解，生成可行调度策略。
- 理论保证：算法近似比为$L+1$（$L$为任务依赖树的高度）。
3. 在线调度算法设计
- 核心思想：在每一时隙$t$，选择收益-时间比（reward-to-length ratio）最高的活跃任务组执行。
- 竞争比分析：证明在任务松弛度（slackness）满足$d_i - ai + 1 \geq l{\text{max}} + li - 1$时，算法竞争比为$4\delta\lambda$（$\delta = l{\text{max}}/l_{\text{min}}$, $\lambda$为依赖链收益比）。
4. 实验验证
- 场景设置：模拟两种典型场景，任务数$N \in [50, 500]$，时间跨度$T=200$，分5个批处理组。
- 性能指标：对比算法效用与最优解比值$\upsilon$。
- 结果：
- 离线算法在树状依赖下平均效用达最优解的60%-80%；
- 在线算法在松弛条件下效用稳定在最优解的40%以上。
主要结果与逻辑关联
- 理论复杂性：证明离线问题为NP难，在线问题无有限竞争比算法（Theorem 1 & 3），为算法设计提供理论边界。
- 算法性能：
- 离线算法通过任务图建模和LP舍入，将问题复杂度从指数级降至多项式级；
- 在线算法通过动态优先级调度，在有限信息下实现实用性能。
- 实验验证：数值实验表明算法在依赖深度（|a_i|）和任务数增加时性能稳定，验证理论分析的紧密度。
结论与价值
科学价值
- 理论贡献：首次系统建模依赖批处理任务调度问题，填补了依赖约束与批处理能力联合优化的研究空白。
- 算法创新：提出的MWRIS转化方法和着色舍入策略为类似调度问题提供新思路。
应用价值
- 工程场景：适用于无线网络多播、数据库锁调度等需兼顾依赖与批处理的资源分配场景。
- 扩展性：树状依赖的结论为后续研究更复杂的DAG依赖奠定基础。
研究亮点
- 问题新颖性：首次将依赖约束与批处理能力纳入统一调度框架。
- 方法创新：
- 离线算法通过任务图与MWRIS转化，结合LP松弛与着色舍入，平衡效率与最优性；
- 在线算法提出收益-时间比动态优先级，适应实时性需求。
- 理论严密性：完整证明问题复杂性和算法性能下界，为后续研究提供基准。
其他有价值内容
- 实验参数敏感性分析：揭示了任务松弛度对在线算法性能的关键影响，为实际系统参数设计提供指导。
- 开源潜力：未提及代码公开，但LP求解和着色算法可复现，适合工业界适配优化。
（注：全文约2000字，涵盖研究全流程的核心细节与逻辑链条。）