第36卷第3期邢台职业技术学院学报Vol.36No.32019年6月Journal of Xingtai Polytechnic College Jun.2019
收稿日期：2019—03—05
作者简介：于倩（1989—），女，河北邢台人，邢台职业技术学院，助教。
92
关于汽车总装线配置问题的数学模型
于倩，郝全枝，宋景红，张洁
（邢台职业技术学院，河北邢台054035）
摘
要：研究了2018年“高教社杯”全国大学生数学建模竞赛D 题，该题是在满足品牌、配置、
动力、驱动、颜的装配要求下，完成车辆在总装线上的装配排序且具有较低的生产成本。利用启发式算法，针对附件中的数据，根据五种装配要求的高低，对其进行组合优化，分层交叉分析设计了汽车总装线排序问题的可行算法。根据设计的排序算法，给出了一天的装配生产顺序，进而验证了设计的合理性。
关键词：装配排序；启发式算法；组合优化中图分类号：O223;TP18
文献标识码：A
文章编号：1008—6129（2019）03—0092—06
一、问题背景
某汽车公司生产多种型号的汽车，每种型号由品牌、配置、动力、驱动、颜等5种属性确定。品牌分为A1和A2两种，配置分为B1、B2、B3、B4、B5和B6六种，动力分为汽油和柴油两种，驱动分为两驱和四驱两种，颜分为黑、白、蓝、黄、红、银、棕、灰、金九种。
公司每天可装配各种型号的汽车460辆，其中白班、晚班（每班12小时）各230辆。每天生产各种型号车辆的具体数量根据市场需求和销售情况确定。
由于工艺流程的制约和质量控制的需要以及降低成本的考虑，对经过生产线的车辆型号有多种装配要求。由于该公司的生产线24小时不间断作业，各项要求对相邻班次（包括当日晚班与次日白班）的车辆同样适用。
公司的装配流程如图1所示。待装配车辆按一定顺序排成一列，首先匀速通过总装线依次进行总装作业，随后按序分为C1、C2
线进行喷涂作业。
图1装配流程图
该企业给出了未来一周的生产计划，根据生产线上的装配要求，本文针对17日~20日的生产计划进行分析，设计算法，使其能给出符合要求且具有较低生产成本的装配顺序。
本问题是在满足品牌、配置、动力、驱动、颜的装配要求下，完成车辆在总装线上的装配排序且具有较低的生产成本。这个问题是NP 难题，本文设计了求解该问题的可行算法，针对附件中的数据，给出了20日的装配顺序。
二、生产计划及装配要求分析
（一）生产计划分析
对该企业给出的生产计划进行分析，结果如表1所示。
表1企业生产计划分析结果
品牌A1A2
动力汽油、柴油汽油、柴油
驱动两驱、四驱两驱、四驱
配置B1,B2,B3,B5B1,B4,B5,B6
颜黑、白、银、灰、黄、红、蓝（7种）黑、白、棕、银、灰、红、蓝、金（8种）
不同无棕和金无黄
当天要完成的工作量较多当天要完成的工作量较少
黑和白汽车数量较多，且黑数量接近
或多于当天总工作量的一半数量
17~20日黑汽车数量较多，且黑数量多于当
天总工作量的一半数量
四驱汽车总数相对于两驱汽车总数较少，容
易满足汽车装配驱动要求
四驱汽车总数相对于两驱汽车总数较少，不容易
满足汽车装配驱动要求
B1数量最多，其次是B2
B1数量最多，其次是B4
黑数量最多且大于当天数量的一半
相同A1和A2品牌都只有B1配置有柴油且数量较少四驱汽车只出现在黑白银灰汽车中
（二）汽车装配要求分析
1.汽车装配流程总要求
汽车在整个流程中需要满足的要求总结如下：
（1）每天白班和晚班都是按照先A1后A2的品牌顺序，分别装配当天两种品牌各一半数量的汽车。
（2）该公司的生产线24h不间断作业，总装线和喷涂线的各项要求对相邻班次（包括当日晚班与次日白班）的车辆同样适用。
（3）尽可能的降低成本。
2.汽车装配对驱动和动力的要求分析
四驱汽车连续装配数量不得超过2辆，两批四驱汽车之间间隔的两驱汽车的数量至少是10辆；柴油汽车连续装配数量不得超过2辆，两批柴油汽车之间间隔的汽油汽车的数量至少10辆。若间隔数量无法满足要求，仍希望间隔数量越多越好。间隔数量在5~9辆仍是可以接受的，但代价很高。
3.总装线作业对汽车颜要求分析
总装线上颜装配顺序要求如表2所示。
表2总装线上颜装配顺序
必须连排黑，连排数量50~70之间，且两批之间间隔至少20
可以连排白银灰棕
必须间隔蓝与白
黄或红与银灰棕金
金首选与黄红，其次与银灰棕
可以间隔银或灰与黄红金
棕与黄红金白
93
汽车模型品牌
白与蓝棕
备注黄和红的排列要求相同
银和灰的排列要求相同
根据“没有允许即为禁止”的原则，两批黑汽车之间必须插入其他颜汽车，除去必须颜要求，黑可以与白银灰棕间隔排列
银灰棕两两不允许间隔排列
4.喷涂线作业对汽车颜要求分析
喷涂作业时，要求蓝、黄、红三种颜在C1线，金在C2线。为了降低颜切换带来的成本，喷涂线C1和C2上尽量安排同一种颜。通过观察公司的装配流程图（图1），总装线上的奇数位车辆都流向了喷涂作业的C1线，而总装线上的偶数位车辆都流向了喷涂作业的C2线，也就是说，喷涂线上对汽车颜的要求可以转化为总装线上对汽车颜的要求。总装线上对颜的要求总结如下：（1）蓝、黄、红三种颜必须在总装线的奇数位；金必须在总装线的偶数位。
（2）在满足总装线的颜要求下，尽可能使颜连续间隔排列，如：白蓝白蓝白蓝白蓝白…
（3）喷涂线上，黑与其他颜切换代价很高。
三、模型的建立
根据对生产计划和汽车装配要求的分析，模型就是要寻满足要求且成本最低的最优配置顺序。
汽车总装线上有驱动、动力和颜三项要求。因为汽车在装配过程中对颜排列顺序的限制较多且为硬性要求，即，不满足则禁止。但是对于驱动、动力的要求也可以通过提高成本来满足，鉴于此，我们优先考虑汽车颜的排列顺序。
（一）确定黑汽车的排列顺序
汽车在整个装配流程中，每天白班和晚班都是按照先A1后A2的品牌顺序，装配当天两种品牌各一半数量的汽车。
对于A1品牌，每天需完成的黑汽车总量（约有180辆）接近或多于当天A1品牌工作量的一半。在装配线上，要求黑连排数量50~70之间，且两批之间间隔至少20，那么180辆黑汽车至少分为3批完成。根据要求，每天白班和晚班分别装配当天A1和A2两种品牌总数量的一半，则需要在白班或晚班的其中一个班次中完成两批黑汽车装配。在模型的设计中，对于A1品牌，我们决定在白班中完成两批黑汽车的装配，每批数量待定。
对于A2品牌，黑汽车总量接近或多于当天A2品牌工作量的一半（大约为46辆）。为了减少黑与其他颜的切换，在模型的设计中，安排黑汽车占用白班和晚班两个班次完成且有一个班次全为黑汽车。
最终，本文设计如表3的排序模型。因为A1品牌晚班装配与A2品牌白班和A2品牌晚班的装配是相邻班次，所以根据黑连排限制，可以在A1品牌晚班的两端考虑是否装配黑汽车。
确定在17~20日中，一个工作日的汽车装配安排。
94
因为A1品牌的白汽车数量较多，在A1品牌白班中，全部用白汽车间隔黑汽车。那么在A1品牌晚班中，需要装配所有非黑汽车。同时，为了减少装配顺序的复杂性，在A1品牌白班中在保证黑汽车
最少的情况下，尽量多的插入四驱汽车。四驱汽车连续装配数量不得超过2辆，两批四驱汽车之间至少安排10辆两驱，黑连排要求数量是50~70。由此确定A1品牌白班中第一批黑数量为60辆，其中最多有10辆四驱汽车；第二批黑数量为48辆，其中最多可有8辆四驱，但是整周工作日的装配计划中黑四驱最多为15辆，这样只要求最多可有6辆四驱即可，且从前到后间隔。
为了使第二批黑连排数量达到50以上，A2品牌白班开始时安排两辆黑四驱。同时，这样装配可以利用A1品牌中的汽车减少两辆A2品牌中四驱汽车。然后，为了不使黑连排数量超过70，接下来装配A2品牌中所有非黑汽车。然后用黑汽车来满足当天工作量的一半。
为了使A2品牌白班中的黑汽车满足连排要求，在A1品牌晚班开始时安排适量的黑汽车。那么A1品牌中剩余的黑汽车全安排在第二批中，其后安排的间隔车辆颜只有白蓝两。为了使得A2品牌晚班的黑汽车满足连排要求，在其上个班次的白汽车后面排列适量黑汽车。最后，A1品牌晚班中第二批黑汽车前面用剩余的其它颜汽车来间隔。
至此，完成了一个工作日黑汽车与非黑汽车的装配顺序。用表4示意如下：
表4装配顺序（1日）
（三）确定其他颜汽车的排列顺序
根据总装线、喷涂线分别对汽车颜要求，建立非黑汽车的排列顺序。
现在对表4中A1品牌的其他颜设计装配顺序模型。A1品牌无棕和金，在确定黑汽车数量时安排了白和蓝汽车的顺序，那么只需确定黄红银灰四种颜排列顺序。黄红两种颜不能连续排列，之间不能间隔排列，只能与银灰间隔排列；银灰两种颜可以分别连续排列或与黄红间隔排列。由此，只需插入银灰两种颜后保证黄红在奇数位上即可。
接下来对表5中A2品牌的其他颜设计装配顺序模型。剩余的其他颜只有两种情况白、棕、银、红、蓝、金（无黄、灰）或白、棕、银、灰、红、蓝、金（无黄），并且红数量完全可以间隔开金，那
么首先选用红间隔开金。白、棕、银、红、蓝、金的排列顺序必须满足的条件如下：（1）白必须间隔开蓝，即蓝必须是白蓝白出现。
（2）红必须间隔开金，即金必须是红金红出现。
（3）银棕不能间隔排列。
（4）白银不能间隔排列。
（5）白红不能间隔排列。
不考虑数量，将“白蓝白”、“红金红”、银、棕按照上述要求排列，共得到两种排列方法：
或者顺序颠倒，即…白蓝白…棕…红金红…银…
…银…红金红…棕…白蓝白…
其中，符号“…”表示可以间隔或连续排列的颜。
对白、棕、银、灰、红、蓝、金的情况而言，即多一种灰。而灰与银需要满足的条件完全相
95
同，也就是说不能排列银的位置也不能排列灰，同时银灰不能间隔排列。那么将棕或红与灰间隔排列后插入到“…”，将多余的灰连排。
四、模型的分析及验证
因为配置的切换和喷涂线上黑与其他颜的切换不可避免，本文设计的方法尽可能减少了黑与其他颜的切换和最大力度满足驱动、动力要求，从而降低成本。
根据本文设计的算法，确定20日的装配顺序（见表5），进而验证算法的合理性。
表5装配顺序（20日）
装配顺序品牌配置动力驱动颜装配顺序品牌配置动力驱动颜
1-40A1B1汽油两白226A2B1汽油两黑41-42A1B1汽油四黑227A2B1柴油两黑43-52A1B1汽油两黑228-230A2B1汽油两黑53-54A1B1汽油四黑231-238A1B1汽油两黑55-64A1B1汽油两黑239-264A1B2汽油两黑65-66A1B1汽油四黑265-266A1B1汽油四银67-76A1B1汽油两黑267A1B1汽油两红77-78A1B1汽油四黑268A1B1汽油两银79-88A1B1汽油两黑269A1B1汽油两红89A1B1汽油四黑270A1B1汽油两银90A1B2汽油四黑271A1B1汽油两红91-133A1B1汽油两白272A1B3汽油两银134-135A1B2汽油四黑273A1B2汽油两红136-145A1B1汽油两黑274A1B2汽油两灰146-147A1B5汽油四黑275A1B2汽油两黄1
48-181A1B1汽油两黑276A1B3汽油四银182-183A2B1汽油四黑277A1B1汽油两黄184A2B1柴油两白278A1B1汽油两灰185A2B1汽油两蓝279A1B1汽油两黄186A2B4汽油两白280A1B1汽油两灰187A2B4汽油两蓝281A1B1汽油两黄188A2B4汽油两白282A1B1汽油两灰189-190A2B1汽油四白283A1B1汽油两黄191-192A2B4汽油两棕284-287A1B1汽油两灰193A2B4汽油两红288-290A1B3汽油两灰194A2B4汽油两棕291A1B5汽油四灰195A2B4汽油两红292-340A1B2汽油两黑196A2B4汽油两棕341A1B3汽油两黑197A2B4汽油两白342A1B1汽油两白198-199A2B1汽油四白343A1B1汽油两蓝200A2B4汽油两棕344A1B1汽油两白201A2B1汽油两红345A1B1汽油两蓝202A2B1汽油两金346A1B1汽油两白203A2B1汽油两红347A1B1汽油两蓝
96