#创作计划#进阶烙饼问题最优调度的公式

yulinOvO

2025-05-28 08:53:04

发布于：重庆

32阅读

0回复

0点赞

Ⅰ-言

灵感来源于#创作计划#烙饼问题最优调度的简单公式

Ⅱ-启

在经典烙饼问题中，我们假设每张饼的两面烙制时间相同（均为 ( $t$ ) 分钟），并通过公式 ( $T = \lceil \frac {2n}{m} \rceil t$ ) 计算最短时间。然而，现实场景中，饼的厚度、材质差异可能导致两面烙制时间不同（如第一面需 ( $t_1$ ) 分钟，第二面需 ( $t_2$ ) 分钟）。此时，简单的并行策略失效，需重新建立数学模型。

Ⅲ-定

(n): 饼的数量（每张饼有两面，但可能一面像铁板，一面像薯片）。
(m): 灶台数量（每个灶台一次只能处理一个饼的一面）。
($t_{i1}, t_{i2} $): 第 ( $i$ ) 张饼的第一面和第二面烙制时间。

Ⅳ-思

①贪心策略

规则：优先烙制剩余时间最长的饼面，这种在普通烙饼问题中可以生效的规则，能否在进阶问题生效呢？

反例（( $n=2, m=2$ )）：

饼 1: $(t_{11}=3, t_{12}=1 )$ ；饼 2: $( t_{21}=1, t_{22}=1 )$ 。
贪心结果：( $T=5$ ) 分钟（存在灶台闲置）。
更优解：( $T=4$ ) 分钟（通过调整顺序避免等待）。

结论：贪心策略无法保证全局最优，还有什么算法可以求最优解来着？

②动态规划

状态定义：

用数字表示每张饼的状态（ $0$ : 未开始； $1$ : 第一面完成； $2$ : 已完成）。

转移方程：
$ [ T (S) = \min\_{\text {可行动作}} \left ( \text {当前时间} + \text {占用灶台时间} \right) ] $
复杂度：( $O (3^n \cdot m)$ )，纯搞笑来的...