「日志】写在51mcm之后：最终发现无需追忆昨天

思い出(无需) なんか(追忆) いらん(昨天)

思い出なんかいらん(无需追忆昨天)

兵库县代表——稻荷崎高中男子排球部赛场横幅古馆春一作品「ハイキュー！！」（排球少年！！）

Intro

大概是这次的劳动节兼青年节假期，我与计划于秋天一起参加cumcm的前辈们参加了51mcm，是中国矿业大学组织的数学建模竞赛。我们所选的题目，是关于运筹与规划的题目A，疫苗生产问题：

新冠肺炎肆虐全球，给世界带来了深重的灾难。各国为控制疫情纷纷研发新冠疫苗。假定疫苗生产需要经过 $CJ_1$ 工位、 $CJ_2$ 工位、 $CJ_3$ 工位以及 $CJ_4$ 工位等4个工艺流程。每个工艺流程一次性均能处理100剂疫苗，这100剂疫苗装进一个加工箱一起送进工位的设备进行处理。而且，只有按照 $CJ_1 \rightarrow CJ_2 \rightarrow CJ_3 \rightarrow CJ_4$ 的顺序在4个工位都进行了加工以后，才算完成生产。为防止疫苗包装出现混乱，某疫苗生产公司生产部门规定，每个工位不能同时生产不同类型的疫苗，疫苗生产不允许插队，即进入第一个工位安排的每类疫苗的生产顺序一旦确定就要一直保持不变，而且前一种类型的疫苗离开某个工位后，后一种类型的疫苗才能进入这个工位。

现有 $YM_1$ 至 $YM_{10} $ 等10种不同类型的疫苗需要生产。为安全起见，每种类型每箱（内装疫苗100剂）疫苗在每个工位上均进行了50次模拟生产。发现，由于生产设备、疫苗纯化等多种原因，每个工位生产不同类型的每箱疫苗所需的时间并不稳定，详细的数据见附件1。

T1: 请对每箱疫苗在所有工位上的生产时间进行均值、方差、最值、概率分布等统计分析，以方便疫苗生产公司管理者能够直观的掌握每个工位生产疫苗的能力水平，为疫苗生产提供参考。

T2: 某国疫苗检测部门紧急需要 $YM_1 \rightarrow YM_{10} $ 各100剂疫苗进行检测。为赶时间，疫苗生产公司需要对疫苗的生产顺序进行规划，以便能在最短时间内交付，以每个工位生产每箱疫苗平均时间为依据。请建立数学模型，制定疫苗生产顺序，初始时刻为00:00，计算生产总时间，并将结果填入表1。
…

Model Building

在pandas库的帮助下，T1我们几乎是秒杀的，顺便完成了所有数据的初步清洗与预处理。但是我们来到T2时便遇上了麻烦。

面对T2我们首先想到的是排队论，但在梳理了排队论的基本方法与使用情况之后，转而想到dp (Dynamic Programming, 动态规划)，但奈何状态转移方程死活写不出来，最终放弃了dp，决定沿用前人的「零件加工」思路：

设疫苗 $YM_k$ 在工位 $l$ 加工所需时间为 $t_{k, l} $ ，从加工系统开始运作直到疫苗 $YM_k$ 在工位 $CJ_l$ 加工完成所需时间为 $s_{k, l} $ ，如若预先指定加工顺序，则进入加工的第 $k$ 类疫苗在工位 $CJ_l$ 加工所需时间设为 $\tau_{k, l} $ ，其在工位 $l$ 加工完成所需时间设为 $\sigma_{k, l} $。

1. 指定顺序的方式有 $A_{10}^{10} = 10!$ 种，可以在原本的类型编号与指定顺序之间建立在数集 $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ 上的 映(一一)射(对应) 关系 $k^{(1)} = \phi(k)$ ，满足

   $$t_{\phi(k), l} = \tau _{k, l}$$ $$s_{\phi(k), l} = \sigma_{k, l}$$

2. 考虑指定顺序后的加工过程：工位 $CJ_1$ 中上一类进行加工的疫苗在完成加工后，紧接着可以安排下一类疫苗进入该工位进行加工，由此可知进入加工的第 $k$ 类疫苗完成在工位 $CJ_1$ 加工完成所需时间为

   $$\sigma_{k, 1} = \sigma_{(k - 1), 1} + \tau_{k, 1}$$

3. 而对于在工位 $CJ_2$ 上的疫苗进行加工的情况而言，需要分情况讨论：

   • $ \sigma_{k, 1} < \sigma_{(k - 1), 2} $
     此时第 $k$ 类疫苗需等待至第 $(k - 1)$ 类疫苗在工位 $CJ_2$ 加工完成之后，方能进入该工位开始加工，因此再考虑其在工位 $CJ_2$ 上进行加工所需时间，第 $k$ 类疫苗在工位 $CJ_2$ 完成加工所需时间

     $$\sigma_{k, 2} = \sigma_{(k - 1), 2} + \tau_{k, 2}$$

   • $ otherwise $
     此时第 $k$ 类疫苗无需等待即可直接进入工位 $CJ_2$ 进行加工，因此其在工位 $CJ_2$ 完成加工所需时间

     $$\sigma_{k, 2} = \sigma_{k, 1} + \tau_{k, 2}$$

   综上所述，第 $k$ 类疫苗在工位 $CJ_2$ 完成加工所需时间

   $$\sigma_{k, 2} = max\{ \sigma_{(k - 1), 2}, \sigma_{k, 1} \} + \tau_{k, 2}$$

4. 同理，对于在工位 $CJ_3$ 与 $CJ_4$ 的疫苗，完成加工所需时间分别为

   $$\sigma_{k, 3} = max\{ \sigma_{(k - 1), 3}, \sigma_{k, 2} \} + \tau_{k, 3} \\ \sigma_{k, 4} = max\{ \sigma_{(k - 1), 4}, \sigma_{k, 3} \} + \tau_{k, 4}$$

5. 由此，如若我们 定(强行)义(规定) 索引为零的情况：

   $$k = 0 时, \phi(0) = 0, 且满足 \\ t_{0, l} = \tau _{0, l} \equiv 0 \\ s_{0, l} = \sigma_{0, l} \equiv 0$$

   根据题意，所有疫苗在进入加工前所占用时间不在题目的考虑范围之内，因此 $\forall k \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ 有

   $$s_{k, 0} \equiv 0 \\ \sigma_{k, 0} = s_{\phi(k), 0} \equiv 0$$

6. 在上一步的简化下，加工过程中所有时间的计算可以简化为

   $$\sigma_{k, l} = max\{ \sigma_{(k - 1), l}, \sigma_{k, (l - 1)} \} + \tau_{k, l}$$

经过以上各步，最后一类（即第十类）在最后的工位 $CJ_4$ 完成加工所需时间 $\sigma_{10, 4} $ 即为我们所求的加工所用的总时间。

Programming

进入加工的第 $k$ 类疫苗在工位 $CJ_l$ 加工时间（即上文定义的 $\tau_{k, l} $ ）设为变量producing_time[k, l]，在工位 $CJ_l$ 加工完成所需时间设为递归函数processing_time(k, l)，则上述过程用程式表述如下

proctime.py

def processing_time(k = 10, l = 4):
    return (max(processing_time(k - 1, l), processing_time(k, l - 1)) + producing_time[k, l]) if (k and l) else 0

正如上文所说，共有 $10!$ 种排列方法，我们在此回给出的解决方案便是枚举这 $10!$ 种排列方法。

References

¹. Norstc的CSDN文章 排队论简介 ↩

². Leetcode力扣的知乎回答 怎样学好动态规划？ ↩

³. 阮行止的知乎回答 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ ↩

⁴. pks-LOVING的洛谷博客 Junior Dynamic Programming——动态规划初步·各种子序列问题 ↩

⁵. sunyueqinghit的CSDN文章 数学建模之排队论 ↩

⁶. 百度百科词条 动态规划 ↩