2022年中国研究生数学建模竞赛C题
*汽车制造涂装-总装缓存调序区调度优化问题*
*一、背景介绍*
汽车制造厂主要由焊装车间、涂装车间、总装车间构成，每个车间有不同的生产偏好，如：焊装车间由于车身夹具的限制偏向最小车型及配置切换生产，涂装车间由于喷漆（固定每5辆车清洗喷头、颜色切换也需清洗喷头）限制偏向颜色以5的倍数切换生产，总装车间由于人员工时（不同车型及配置人员工时不同）及硬件（零部件数量等）等限制偏向按照车型及配置按比例切换生产。
由于各车间的约束不同导致生产调度无法按照同一序列连续生产，特别是涂装车间与总装车间序列差异较大，这就需要在两个车间之间建立一个具有调序功能的缓存区，即PBS（Painted Body Store，汽车制造涂装-总装缓存调序区），用来将涂装车间的出车序列调整到满足总装车间约束的进车序列。
目前，一天安排上线生产的车辆数介于200-450之间，对于每天要上线生产的车辆，车型、颜色等属性均有变化，目前车型大类有2种，颜色大约有10种，各个车间的产能不定，主要根据当天生产安排调整，涂装车间及总装车间的工艺流程如下：
l 涂装车间处理喷漆工艺，主要是将涂料涂覆于白车身表面，最终形成涂膜或者漆膜或者涂层。涂装车间的详细流程如图1所示，主要是将白车身经过前处理电泳-中涂-色漆-清漆，最终得到修饰完整的车身。
图1 涂装车间工艺流程图
l 总装车间处理装配工艺，主要是组装剩余零部件，得到最终成品车辆。总装车间的详细流程如图2所示，主要由内饰线、底盘线、最终线组成，最终经过测试检验后，成品车辆下线入库。
图2 总装车间工艺流程图
*二、问题描述*
根据涂装车间的出车序列通过PBS调度调整得到总装车间的进车序列。PBS具体信息如图3所示。
图3 涂装-总装缓存调序区（PBS）示意图
PBS由涂装-PBS出车口、接车横移机、进车道6条（每条进车道有10个停车位、FIFO结构）、返回道1条（有10个停车位）、送车横移机及PBS-总装接车口等7个区域组成。各车道距离等分，每车道宽度2米，两相邻车道间间隔1米。横移机运动时的速度保持一致。
l*数据示例：*
| 进车顺序 | 车型 | 动力 | 驱动 |
| 1 | A | 混动 | 两驱 |
| 2 | B | 混动 | 两驱 |
| 3 | A | 燃油 | 两驱 |
| 4 | B | 燃油 | 两驱 |
| 5 | A | 燃油 | 四驱 |
| 6 | B | 燃油 | 四驱 |
l*PBS接车横移机：*
\1. 将车身从涂装-PBS出车口运送到合适进车道。
\2. 将车身从返回道运送到合适进车道。
l*PBS送车横移机：*
\1. 将所选择车身从进车道运送到PBS-总装接车口。
\2. 将需调序车身从进车道运送到返回道。
l*PBS约束说明：*
\1. 送车横移机不能将返回道的车身送入PBS-总装接车口。
\2. 车身在进车道和返回道的移动方向为图中标注方向，不得改变。
\3. 接车横移机和送车横移机上同一时刻分别最多有一个车身。
\4. 接车横移机和送车横移机在完成任意动作后，必须返回中间初始位置，才可以执行下一步动作。
\5. 接车横移机和送车横移机在执行任何动作过程中，均不能被打断。
\6. 当返回道10停车位有车身，同时接车横移机空闲时，优先处理返回道10停车位上的车身。
\7. 当若干进车道1停车位有车身等候，同时送车横移机空闲时，优先处理最先到达1停车位的车身。
\8. 如果任意进车道1停车位有车身，那么送车横移机不能设置为空闲状态。
\9. 进车道和返回道每个时刻最多容纳10个车身，每个停车位最多容纳1个车身。
\10. 同一车道内，多个车身在不同停车位上的移动可以不同步进行。
\11. 当某车身所在停车位的下一停车位出现空位时，车身必须立即开始向下一停车位移动。
\12. 车身在进车道和返回道不同停车位之间移动的过程中，不能被调度。
l*PBS相关时间数据说明：*
\1. 假定车身由横移机卸载到各进车道10停车位或返回道1停车位，以及由各进车道
1停车位或返回道10停车位装载到横移机上的时间均可忽略。
\2. 假定车身在涂装-PBS出车口处装载到接车横移机上，以及在4车道出口中间位置
处，车身由送车横移机上卸载到PBS-总装接车口，时间均可忽略。
\3. 进车过程：任意车身到达涂装-PBS出车口时，处于最中间位置，正对进车道4，
接车横移机把车身从该位置运送至不同进车道10停车位并返回至初始位置，对于
1-6进车道，消耗时间分别为[18, 12, 6, 0, 12, 18]秒。
\4. 出车过程：送车横移机从中间初始位置出发，把各进车道1停车位的车身运送至总
装-PBS接车口，处于最中间位置，正对进车道4，对于1-6进车道，消耗时间分别
为 [18, 12, 6, 0, 12, 18] 秒。
\5. 车进返回道过程：在有需要时，送车横移机从中间初始位置出发，把各进车道1停
车位的车身，运送至返回道1停车位，并返回至初始位置，对于1-6进车道，消耗
时间分别为 [24, 18, 12, 6, 12, 18]秒。
\6. 车出返回道过程：接车横移机从中间初始位置出发，把返回道10停车位的车身，
运送至任意进车道10停车位并返回至初始位置，对于1-6进车道，消耗时间分别
为 [24, 18, 12, 6, 12, 18] 秒。
\7. 车移动过程：任意车身在进车道/返回道中，从某一停车位移动至后一停车位，消
耗时间为 9秒。
l*可选的调度手段：*
\1. 接车横移机将当前涂装-PBS出车口队列第一个车身或者返回道10停车位的车身送入任意进车道的10停车位。
\2. 送车横移机将任意进车道1停车位的车送入返回道1停车位或者PBS-总装接车口。
\3. 接车横移机和送车横移机均可以在一段时间内被设置为空闲状态。
l*输入输出：*
\1. 输入：涂装出车序列清单，可提供多个数据清单。
\2. 输出：每个车身在每一秒所处的区域（涂装-PBS出车口、接车横移机、任意进车
道任意停车位、返回道任意停车位、送车横移机、PBS-总装接车口），可构建二维矩阵，里面存储区域代码（如200辆车在第1000秒完成全部调度，则需提交200*1000的矩阵）。矩阵中每一个值为各个区域代码，总的区域代码有74个，区域与代码的对应关系见附件3。车身不在上述74个区域时，对应矩阵值为空白。具体的输出模板文件见附件4（模板文件只是一个示意，示意的场景是50个车身在第100秒完成全部调度，每行代表每个车身各个时间点所处区域，每列代表每个时间点各车身所处区域，其中区域代码没具体填写，具体区域代码见附件3；具体的输出矩阵，需要根据实际数据和算法计算得到，相关数据见附件1-3，附件4只是示意，不代表本题只有50个车身）。由于PBS相关时间说明第1、第2两条假设，会出现同一时刻车身处于若干不同区域的情形，则在输出矩阵该车身该时刻对应格子中填入这些区域中最后一个区域的代码。例如，第0秒，如果涂装-PBS出车口第一个车身（1号车身）被装载到接车横移机上，接着被卸载到4进车道10号车位，则在1号车身第0秒格子中填入4进车道10号车位的区域代码“410”；又例如，第75秒，如果5号车身从送车横移机上被卸载到PBS-总装接车口，则在5号车身第75秒格子中填入PBS-总装接车口区域代码“3”。
l*优化目标：*
\1. 混动车型间隔2台非混动车型为优，权重系数 0.4。
\2. 四驱车型与两驱车型倾向1:1出车序列，权重系数 0.3。
\3. 返回道使用次数倾向于0，权重系数 0.2。
\4. 倾向总调度时间越短越好，权重系数 0.1。
*注：*该权重系数用于多目标得分加权，各权重系数相加等于1。
l*优化目标具体量化逻辑：*
设置每个优化目标初始分，根据下述逻辑更新得分后，再乘以相应系数，得到最终加权总分（理论最高分100分）。
\1. 优化目标1（权重系数0.4，初始分100分）：检查出车序列，找到所有混动车身，从出车序列头部按照先后顺序开始算，计算每连续两辆混动车身之间的非混动车身数，不等于2则扣1分。
\2. 优化目标2（权重系数0.3，初始分100分）：对出车序列进行分块，判断每一分快中的四驱车型与两驱车型之比是否满足1:1，若不满足，则扣1分。对出车序列分块的依据是：如果序列以4开头，则根据从2变为4将序列进行分块；如果序列以2开头，则根据从4变为2将序列进行分块。 例如：如果出车序列为 442242444224(4代表四驱车型，2代表两驱车型)，则该序列分块结果为：4422,42,44422，4，最后两个分块44422和4都不满足1:1，扣2分。
\3. 优化目标3（权重系数0.2，初始分100分）：统计返回道使用次数，每使用一次扣1分。
\4. 优化目标4（权重系数0.1，初始分为100分）：假设出车队列长度为C， 第一辆车身进入涂装-PBS出车口时刻记为零，以最后一个车身进入PBS-总装接车口的时刻T为总完成时间，其理论最快完成时间为 9C+72(全部走进车道4，出车序列与入车序列相同)，其时间惩罚值设置为 0.01 × (T – 9C-72)， 最后目标得分为 100 – 时间惩罚值。
*请建模完成以下优化问题：*
*问题 1*：严格按照PBS约束说明及相关时间数据说明，根据涂装出车序列，考虑PBS区域调度能力及限制，建立PBS优化调度模型，使得总装进车序列尽可能满足总装生产需求。给出将你们的优化调度方案分别应用于附件1和附件2数据的得分结果，并将使用附件1和附件2两套数据的调度输出结果按照附件4格式分别存入result11.xlsx和result12.xlsx。
*问题 2*：如果去除PBS约束说明中第6、7两条约束，其余约束不变，根据涂装出车序列，考虑PBS区域调度能力及限制，建立PBS优化调度模型，使得总装进车序列尽可能满足总装生产需求。给出将你们的优化调度方案分别应用于附件1和附件2数据的得分结果，并将使用附件1和附件2两套数据的调度输出结果按照附件4格式分别存入result21.xlsx和result22.xlsx。
l*数据说明：*本题共有两套数据，附件1数据是生产数据脱敏后的正常数据，附件2数据是为了测试模型和算法的适应性而调整后的数据。
参考文献：
\1. Zohali H, Reformulation, linearization, and a hybrid iterated local search algorithm for economic lot-sizing and sequencing in hybrid flow shop problems. Computers & Operations Research, 2019, 104:127-138.
\2. Shen Z, Tang Q, Huang T. Dynamic Production Scheduling Modeling and Multi-objective Optimization for Automobile Mixed-Model Production. Communications in Computer and Information Science, 2018, 924: 25-33.
\3. Jalilvand-Nejad A, Fattahi P. A mathematical model and genetic algorithm to cyclic flexible job shop scheduling problem. Journal of Intelligent Manufacturing, 2015, 26(6):1085-1098.
\4. Boysen N, Zenker M. A decomposition approach for the car resequencing problem with selectivity banks. Computers & Operations Research, 2013, 40(1):98-108.
\5. Yavuz, Mesut. Iterated beam search for the combined car sequencing and level scheduling problem. International Journal of Production Research, 2013, 51(12):3698-3718.
\6. 陈正茂. 基于排序缓冲区的多车间关联排序研究[D]. 华中科技大学, 2008.
