谢帅东
奇瑞汽车河南有限公司 河南 475200
摘要：在现有的生产计划、调度与优化中，通常先对生产计划进行单独优化，然后在被优化的计划基础上对生产调度进行优化，其结果是计划与调度不能实现整体优化，甚至导致生产计划的不可行或性能差的现象。基于此,本文针对汽车装配车间生产计划与调度的同时优化问题，提出了三种新的求解方法，以使综合性能指标达到最小化。
关键词：装配车间；生产计划与调度；优化方法
装配车间的生产管理是汽车企业顺利生产的前提，也是提高企业经济效益的重要条件及保证产品质量的基础性工作。汽车装配车间生产计划与调度的同时优化，是敏捷制造环境下首先要解决的问题。随着汽车品种、批量、混批的变化，所以如何编制及优化汽车装配线的生产计划和调度，控制各装配位的装配节奏，实现负荷均衡，保持与大型生产线相同的资源利用率，已成为能否实现汽车装配敏捷制造的关键。
一、粗生产计划
建立求解最优粗生产计划的混合整数规划模型，其采用分枝定界法或单纯形法求解,得到使各装配工位的资源利用率和准备成本达到整体优化，并尽可能满足产品需求的粗生产计划。
粗生产计划求解方法如图1所示。在这里使用的是ODBC API编制应用程序,实现数据的读取、插入及修改功能。根据平滑定单给出的需求计划,通过单纯形法求得一个最优值,但这个值不一定就是最优的整数解,所以需要对获得的最优解判断其是否为整数解。若为整数解,则将其作为粗生产计划；否则需对其进行分枝定界。
图1 粗生产计划求解程序框图
第一步:分枝,假设原模型问题为问题A,任选其中的一个非整数解,构造两个约束条件。将这两个约束分别加入到原问题上,则分解为两个子问题A1和A2,左分枝增加约束条件≤17得到问题A1,右分枝增加约束条件≥18得到问题A2,求此两个后继子问题的解。
定界,以每个后继问题为一分枝表明求解的结果,与其它问题解的结果相比,找出性能指标最好的作为新的上界。
第二步:比较与剪枝,各分枝中的性能指标值若有大于上界的,则剪掉此枝,否则重复第一步骤，一直到求得整数解为止。分枝定界法求得的粗生产计划是最优的整数解,但随着问题规模的增大,分枝会越来越复杂,其个数以2的指数增加,最多的分枝节点个数为2N。这样问题的复杂度也随之增大,求解的速度明显下降,故当问题复杂度大时(在装配线上指当需求的汽车种类超过10时),直接采用单纯形法求解,然后对求得的解取整。
二、生产计划与调度集成优化的实现
1、数学模型。由其获得的粗生产计划可作为后续生产计划与调度整体优化问题迭代求解的初始计划,以加快问题的求解速度。另外,考虑细节的装配线调度往往是一个非结构化问题,很难用解析的方法求解,较为可行的办法是使用基于可变时间流的快速调度仿真。最后,利用SA算法搜索来解决最优计划与调度的选择问题。此外，为节省汽车装配准备时间,同种汽车集中装配,不分割成多个装配任务,在调度中仅占用一个排序位置。
2、算法实现
1)嵌入式SA算法(ESAA)。其基本思想是:从初始生产计划出发,在计划层用SA算法进行搜索寻找最好的计划,同时对计划层Markov链中随机产生的相邻计划用另一个SA算法搜索，经快速调度仿真计算具有最好性能指标的调度,直至生产计划与调度同时达到优化。
2)交替式SA算法(ASAA)。其基本思想是:①从初始生产计划出发寻找一个可行计划与调度；②给定调度,用SA算法寻找最好的计划；③反过来给定计划,再用另一个SA算法搜索最好的调度；④交替使用②、③两步直至找到最好的计划与调度。由于分别对计划与调度进行SA算法搜索,在此称这种方法为交替式SA算法。
3)串行式SA算法(SSAA)。其基本思想是:①从初始生产计划出发寻找一个可行的计划；②从可行计划开始,使用SA算法寻找最好的计划；③对此最好的计划,使用另一SA算法寻找最好的调度。由于对计划和调度依次使用SA算法,故称为串行式SA算法。
本文以嵌入式SA算法为例对算法流程进行详细分析:
算法1:生产计划与调度集成优化问题嵌入式SA算法。
Step1:初始化
.png)
其中,M_big为一个大数；p0为初始生产计划；为粗生产计划；p*为当前Markov链迭代后所接受的解；p为当前搜索的新解；s**为相应计划的最好调度；PM_len为当前计划SA算法的Markov链中的变换个数；PN_len为当前计划SA算法的Markov链的迭代次数；G(a,b)为对应计划a与调度b的性能指标；P_best为经SA算法搜索到目前为止最好的计划；S_best为经SA算法搜索到目前为止最好的调度；G_best为到目前为止最好的生产计划与调度对应的最好性能指标；flag为生产计划可行与否的标识,可行则为1,否则为0。
算法2:基于SA算法的调度优化。
.png)
Step4:返回
其中,s*为当前调度搜索Markov链迭代后接受的解(旧解)；s为当前调度搜索的新解；s**是针对当前计划p搜索到的最好调度；SM_len为当前调度的SA算法的Markov链中的变换个数；SN_len为当前调度的SA算法Markov链的迭代次数。
三、结论
1、与传统方法相比,本文中的方法优点是将解析方法、模拟退火方法和快速调度仿真有机结合在一起,有效解决了汽车装配线生产计划与调度的集成优化问题,并保证至少有一个可行解。
2、ESAA的问题求解速度最慢,但获得的性能指标往往最好。SSAA的问题求解速度最快,获得的性能指标却往往最差。ASAA介于两者之间。
3、随着问题规模的增大,这三种算法求解问题所需的时间也随之增长,在可接受的时间内,ESAA比较适合于求解小规模问题,ASAA较适合于求解中规模问题,而SSAA则适合于求解大规模问题。
综上所述，敏捷制造是企业为适应日益激烈的市场竞争而采取的新的生产模式,而计划与调度的优化则是制造企业提高生产效率的主要手段。本文提出了三种新方法来解决汽车装配车间生产计划与调度的同时优化问题。
参考文献：
[1]路致远.基于模型重构的生产计划优化系统设计与开发[J].计算机技术与发展,2015(03).
[2]陈琳.汽车装配线生产计划与调度的集成优化方法[J].计算机技术与发展，2015(01).
[3]严洪森.汽车装配车间生产计划与调度的同时优化方法[J].自动化学报,2016(06).