在线目标日期分配问题与在线拨号乘车问题解析

### 在线目标日期分配问题与在线拨号乘车问题解析 在计算机科学和运筹学领域，在线目标日期分配问题（Online Target Date Assignment Problem，OnlineTDAP）和在线拨号乘车问题（Online Dial - a - Ride Problem，OlDarp）是具有重要研究价值的问题。下面将对这两个问题进行详细分析。 #### 在线目标日期分配问题 在线目标日期分配问题主要涉及下游装箱、并行机调度和旅行商问题等多个方面。 ##### 下游装箱问题 在下游装箱问题中，考虑所有请求大小相等的情况。对于该问题，有以下重要结论： - **竞争比下界**：不存在确定性在线算法的竞争比小于 3/2。证明过程如下：设所有请求的大小为 s，考虑任意在线算法 Alg 和请求序列 σ。在日期 0 给出 δ⌊1/s⌋ 个请求，为了使竞争比优于 2，Alg 每天最多使用一个箱子。在日期 1 再给出 (δ + 2)⌊1/s⌋ 个请求，此时 Alg(σ) ≥ 3，而 Opt(σ) = 2。 - **Bal 算法的竞争比**：通过一系列推导可以证明 Bal(σ) < 2 Opt(σ) + 1，这表明 Bal 算法在该问题中有一定的性能保证。 ##### 下游并行机调度问题 当每日期可用机器数量有界（m < ∞）时，对于最小化所有目标日期的最大完工时间的调度问题，有以下结论： - **竞争比下界**：不存在确定性在线算法的竞争比小于 3/2。例如，给定 mδ 个发布日期为 0 且处理时间为 1 的请求，只有将 m 个作业分配到每个日期的算法 Alg 才可能优于 2 - 竞争。但在日期 1 再给出 m(δ + 2) 个处理时间为 1 的请求时，Alg 的最大完工时间至少为 3，而最优最大完工时间为 2。 - **Bal 算法的竞争比**：Bal 算法是 (3 - 1/δ) - 竞争的。证明过程如下：考虑由 Bal 服务的请求序列 σ，设 r 是导致最大完工时间的第一个请求。设 w 是所有可行目标日期中负载最小的机器的负载。Bal 的最大完工时间至多为 w + p(r)，总负载至少为 wmδ + p(r)。即使是最优离线算法 Opt 也至少有 Opt(σ) ≥ (wmδ + p(r)) / ((2δ - 1)m) > wδ / (2δ - 1)，进而可得 w < (2 - 1/δ)Opt(σ)，最终得出 Bal(σ) < (3 - 1/δ)Opt(σ)。 - **特殊情况**：当所有请求的处理时间相等时，下游调度问题等价于均匀物品的装箱问题，Bal 算法是 2 - 竞争的，且不存在确定性在线算法的竞争比小于 3/2。 ##### 旅行商问题 对于以最小化最大下游成本为目标的旅行商问题，有以下结论： - **Bal 算法的竞争比**：Bal 算法是 (2δ - 1) - 竞争的，因为分配到最大游览长度日期的请求最多可分散在 2δ - 1 个日期。 - **竞争比下界**：不存在确定性在线算法的竞争比小于 2。例如，考虑由至少有 δ + 1 个叶子的无权星图诱导的度量空间，在日期 0 给出 δ 个不同叶子的请求，若算法 Alg 在一天分配多个请求，则不能优于 2 - 竞争。在日期 1 再给出相关请求，会使 A