关于汽车总装线配置问题的数学模型

（邢台职业技术学院，河北邢台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日的装配顺序。收稿日期：2019—03—05作者简介:于倩（1989—），女，河北邢台人，邢台职业技术学院，助教。92邢台职业技术学院学报2019年第3期二、生产计划及装配要求分析

（一）生产计划分析对该企业给出的生产计划进行分析，结果如表1所示。表1企业生产计划分析结果品牌动力驱动配置颜色A1汽油、柴油两驱、四驱B1,B2,B3,B5黑、白、银、灰、黄、红、蓝（7种）无棕色和金色当天要完成的工作量较多黑色和白色汽车数量较多，且黑色数量接近不同或多于当天总工作量的一半数量四驱汽车总数相对于两驱汽车总数较少，容易满足汽车装配驱动要求B1数量最多，其次是B2A2汽油、柴油两驱、四驱B1,B4,B5,B6黑、白、棕、银、灰、红、蓝、金（8种）无黄色当天要完成的工作量较少17~20日黑色汽车数量较多，且黑色数量多于当天总工作量的一半数量四驱汽车总数相对于两驱汽车总数较少，不容易满足汽车装配驱动要求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邢台职业技术学院学报白与蓝棕2019年第3期备注黄色和红色的排列要求相同银色和灰色的排列要求相同根据“没有允许即为禁止”的原则，两批黑色汽车之间必须插入其他颜色汽车，除去必须颜色要求，黑色可以与白银灰棕间隔排列银灰棕色两两不允许间隔排列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品牌晚班的两端考虑是否装配黑色汽车。表3排序模型A1品牌白班A2品牌白班其他颜色黑色汽车其他颜色黑色汽车其他颜色黑色汽车A2品牌晚班A1品牌晚班黑色汽车其他颜色黑色汽车其他颜色黑色汽车（二）确定黑色汽车数量确定在17~20日中，一个工作日的汽车装配安排。94邢台职业技术学院学报2019年第3期因为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示意如下：表4A1品牌白班装配顺序（1日）A2品牌白班白色汽车60两驱黑白色汽车A1品牌晚班48两驱黑2四驱黑其他颜色A2品牌晚班黑色汽车黑色汽车其他颜色黑色汽车白蓝白…黑色汽车黑色汽车（三）确定其他颜色汽车的排列顺序根据总装线、喷涂线分别对汽车颜色要求，建立非黑色汽车的排列顺序。现在对表4中A1品牌的其他颜色设计装配顺序模型。A1品牌无棕色和金色，在确定黑色汽车数量时安排了白色和蓝色汽车的顺序，那么只需确定黄红银灰四种颜色排列顺序。黄红两种颜色不能连续排列，之间不能间隔排列，只能与银灰间隔排列；银灰两种颜色可以分别连续排列或与黄红间隔排列。由此，只需插入银灰两种颜色后保证黄红在奇数位上即可。接下来对表5中A2品牌的其他颜色设计装配顺序模型。剩余的其他颜色只有两种情况白、棕、银、红、蓝、金（无黄、灰）或白、棕、银、灰、红、蓝、金（无黄），并且红色数量完全可以间隔开金色，那么首先选用红色间隔开金色。白、棕、银、红、蓝、金的排列顺序必须满足的条件如下：（1）白色必须间隔开蓝色，即蓝色必须是白蓝白出现。（2）红色必须间隔开金色，即金色必须是红金红出现。（3）银棕不能间隔排列。（4）白银不能间隔排列。（5）白红不能间隔排列。不考虑数量，将“白蓝白”、“红金红”、银、棕按照上述要求排列，共得到两种排列方法：或者顺序颠倒，即…白蓝白…棕…红金红…银……银…红金红…棕…白蓝白…其中，符号“…”表示可以间隔或连续排列的颜色。对白、棕、银、灰、红、蓝、金的情况而言，即多一种灰色。而灰色与银色需要满足的条件完全相95邢台职业技术学院学报2019年第3期同，也就是说不能排列银色的位置也不能排列灰色，同时银灰不能间隔排列。那么将棕或红与灰色间隔排列后插入到“…”，将多余的灰色连排。四、模型的分析及验证

因为配置的切换和喷涂线上黑色与其他颜色的切换不可避免，本文设计的方法尽可能减少了黑色与其他颜色的切换和最大力度满足驱动、动力要求，从而降低成本。根据本文设计的算法，确定20日的装配顺序（见表5），进而验证算法的合理性。表5装配顺序1-4041-4243-5253-5455-6465-6667-7677-7879-88899091-133134-135136-145146-147148-181182-183184185186187188189-190191-192193194195196197198-19920020120220396品牌A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2A2配置B1B1B1B1B1B1B1B1B1B1B2B1B2B1B5B1B1B1B1B4B4B4B1B4B4B4B4B4B4B1B4B1B1B1动力汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油柴油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油驱动两四两四两四两四两四四两四两四两四两两两两两四两两两两两两四两两两两白黑黑黑黑黑黑黑黑黑黑白黑黑黑黑黑白蓝白蓝白白棕红棕红棕白白棕红金红装配顺序（20日）装配顺序226227228-230231-238239-264265-266267268269270271272273274275276277278279280281282283284-287288-290291292-340341342343344345346347品牌A2A2A2A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1配置B1B1B1B1B2B1B1B1B1B1B1B3B2B2B2B3B1B1B1B1B1B1B1B1B3B5B2B3B1B1B1B1B1B1动力汽油柴油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油驱动两两两两两四两两两两两两两两两四两两两两两两两两两四两两两两两两两两颜色黑黑黑黑黑银红银红银红银红灰黄银黄灰黄灰黄灰黄灰灰灰黑黑白蓝白蓝白蓝颜色邢台职业技术学院学报204205206207-208209210211212213-214215-216217-224225A2A2A2A2A2A2A2A2A2A2A2A2B1B1B1B4B6B4B6B6B1B1B1B5汽油汽油汽油汽油汽油汽油汽油汽油汽油柴油汽油汽油两两四两两两两两四两两四金红银银红金棕白白黑黑黑348349350-376377-403404405406-411412-435436-453454455-458459-460A1A1A1A1A1A1A1A2A2A2A2A2B1B3B1B2B5B5B3B1B2B5B6B1汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油汽油2019年两两两两两两两两两两两四第3期白蓝白白白黑黑黑黑黑黑白参考文献：[1]莫会霞.汽车总装工艺布局调整及改造的研究与实现[D].长春：吉林大学，2012.[2]刘文平.混合品种汽车装配线平衡与排序问题研究[D].济南：山东大学，2009.[3]高妍，韩艳红.汽车总装线的设计步骤和方法研究[J].应用技术与设计，2017（02）：121.TheMathematicalModelofAutomobileAssemblyLineConfigurationYUQian，HAOQuan-zhi，SONGJing-hong，ZHANGJie

（XingtaiPolytechnicCollege,Xingtai,Hebei054000,China）Abstract:ThispaperstudiesproblemDofthe2018“HigherEducationPressCup”nationalcollegestudentsmathematicalmodelingcontest.Itaimstocompletetheassemblysequenceofvehiclesonthefinalassemblylinewithlowproductioncostundertheassemblyrequirementsofbrand,configuration,power,driveandcolor.Inthispaper,heuristicalgorithmisusedtocombineandoptimizethedataintheattachmentaccordingtotheleveloffivekindsofassemblyrequirements,andhierarchicalcrossanalysisisusedtodesignafeasiblealgorithmforsortingproblemofautomobilefinalassemblyline.Accordingtothedesignsequencingalgorithm,the1-dayassemblyproductionsequenceisgiven,andtherationalityofthedesignisverified.Keywords:assemblysequence;heuristicalgorithm;combinatorialoptimization97