2019年MathorCup高校数学建模挑战赛C题优秀论文.pdf

队伍编号905190

题号C

汽配件生产过程中的排程问题研究

摘要

本文对汽配件生产中喷涂过程的排程问题进行了研究，建立了状态转移向量模型并

加以求解，获得了在不同目标下的排程方案。

在问题分析阶段，本文把303*8个滑橇变化看成一个三维向量的303*8次转移，从

而建立了转移向量模型，所求最优排程矩阵即该向量在约束条件下的最优转移路径。

针对问题一，本文采用粒子群算法求解建立的转移向量模型，大大提高了寻找解的

效率，最终获得了以“换色次数最少”为目标函数的排程矩阵，并求得了平均每圈的换

色次数为3.125次，且能完全满足指导产量需求。

针对问题二，由于目标函数增加了“换支架最少”，变成了两个，单一的粒子群算法

迭代效率十分缓慢。本文采用了基于禁忌搜索的粒子群算法，通过“记忆”功能，有效

地改善了算法的效率，最终得出问题二的排程矩阵，并求得平均每圈换色次数为8.125

次，平均每圈换支架数为39次，且能完全满足指导产量需求。

关键词：状态转移向量；粒子群算法；禁忌搜索；排程矩阵

目录

一：问题重述1

二：模型假设2

三：符号说明2

四：问题一的分析和解答3

4.1状态转移模型的建立3

4.2模型的求解4

4.2.1粒子群算法4

五：问题二的分析与解答9

5.1问题引入9

5.2模型改进9

5.2.1改进方向9

5.2.2模型应用步骤11

5.3模型求解算法12

5.3.1基于禁忌搜索的粒子群优化算法12

5.3.2求解结果13

六：模型的改进17

七：参考文献17

八：附录18

一：问题重述

某汽车零配件制造商的生产流程中的喷涂过程在传送带上完成，传送带轨道

上装有滑橇，滑概在1分钟。一个滑橇有两面，可同时喷涂，一面可以放3个支

架，一个滑橇共可放6个支架，支架类型与零件种类为一一对应关系，每种零件

只能放置在对应的特定橇上装有可拆卸支架，每个零件需要放在特定的支架上进

行顺序喷涂。喷涂过程的一个生产周期称作“一圈”(即将传送带轨道上所有滑橇

上的零件喷涂完毕)，一圈共有303个滑橇，全部喷涂完毕的时间大概在5.5个

小时，一个滑橇喷涂工序节拍大支架上。一个滑橇上只放置同种零件,滑橇不强制

要求摆满支架和零件，但为避免产能浪费，无特殊原因不会放空支架。支架的数

量是有限制的，所以在一圈的生产计划中同种零件的上架数也有对应上限。

放置在支架上的零件顺序经过以下的喷涂工序：底漆(黑底/白底)——面漆

(15种左右)——清漆(高光/哑光)。零件最终的喷涂颜色由面漆决定，每种面漆有

对应的底漆和清漆颜色。若相邻前后两个滑橇上的零件需要喷涂不同的面漆色，

则称为出现了一次“换色”，意味着对应的喷枪需要更换涂料颜色。并且该换色

过程要求在两个滑橇之间插入一个滑橇的底漆件作为过渡，底漆件可以是不同种

零件，但只需要喷涂底漆，将来会作为售后备件使用（此问题中无需明确底漆件

为何种零件）。面漆换色的前后顺序限制规则如下，任意红色和任意蓝色后面不

能接任何白色，极地白后不能安排任意黑色，钻石白前必须是极地白。零件的前

后摆放顺序也有一定限制，并且相同颜色的同种零件应尽量摆放在一起。具体的

颜色前后顺序限制条件由附件给出。喷涂完毕的零件经过人工检查和抛光后入库，

等待装配。

现根据每日交付情况，需要生产线预先生产-批零件以应对未来需求，各种颜

色不同种零件的指导生产量已给出，并预期在未来八圈的生产计划中尽量满足。

请建立数学模型解决下面的问题。

问题1：针对附件中给出的指导生产量制定出未来八圈的详细喷涂排序计划，要

求为了降低生产成本尽量减少换色的次数,并尽可能满足指导生产量的需求(超过

计划生产量的产出是允许的，但不会带来额外的直接收益)。请在论文中列出第

一圈的喷涂计划结果如表1所示，并统计