流水线调度优化模型 武大数模选拔

题目：流水线车间调度优化模型

【摘 要】

通过对问题的分析，流水线车间调度问题可以归结为一个整数规划问题，本论文中根据题目所给的条件以及实际情况依次建立起两个模型。在满足加工时间最短的前提下，基于对问题约束条件不同的翻译得到两个模型从而得到不同的生产顺序，为决策者提供了更多的生产方案。联系生产生活实际情况，放松加工工件必须遵循相对顺序不变这一约束条件，提出模型的改进方向。

模型一，根据题目要求即每个工件的加工顺序为弯折——焊接——装配且每台机器每次只能处理一个加工件。构造一个每行每列只含一个1其余元素为0的矩阵，通过矩阵乘积实现对原来工件工序耗时的行变换，整个过程相当于遍历。建立线性规划模型，利用LINGO软件求解。结果为当加工顺序为4—1—3—6—5—2时，用时最短为35min，利用Excel作出甘特图使整个生产安排流程更加清晰，引入时间利用率的概念即加工工件的时间占开启时间的百分比，得到在加工顺序为4—1—3—6—5—2时机器一（弯折）机器二（焊接）机器三（装配）的时间利用率依次为100%，67.9%，100%，从而可从机器负载评价加工过程。 模型二，将每台机器每次只能处理一个加工件这一约束条件翻译为一旦开始顺序确定，则后续工序仍按原顺序进行。引入0—1变量表示两工件生产顺序，建立0—1规划模型，利用LINGO软件求解。结果为当加工顺序为1—3—6—4—5—2时，用时最短为35min。利用甘特图对结果进行分析与检验，得到3台机器的时间利用效率分别为100??.3%，为决策者选择方案提供了更多的参考指标。

讨论本文所建模型的优点和缺点，横向的对比两个模型。在工件数目相对较多（在十这一数量级上）的情况下选择模型一求解，LINGO可以在短时间内给出答案；在数据量较少的情况下运用模型二求解，因为它模型建立过程简单易懂，编程容易。但是对于工件数目处于百个数量级时，两种模型均无法在短时间内得到答案，需要建立新的模型，设计新的算法求解此类大规模排序问题。 针对模型的部分缺点提出优化改进方案，改变初始工件加工各工序耗时矩阵，即动态设立初始点以弥补LINGO软件只能输出一组最优解的局限，得出当加工顺序为3—1—6—5—4—2，4—1—6—5—3—2，3—4—1—6—5—2，1—4—6—5—3—2时也能使加工时间最短为35min，提供了更多的可选择方案。联系实际生产，根据各机器单位时间的工作成本不同，可以建立多目标规划模型，既要使总的时间最短又要使整个加工过程机器的总成本最低，同时实现时间和成本的最优化。可以为决策者提供更实用的生产工件加工顺序规划。

文末简述了模型的推广与应用。将此线性整数规划模型稍作修改就可以运用到安排面试人员的面试顺序、单机调度最优化、公交车的调度等问题。枚举的思想可以用到一些小规模的排序问题中，利用优化软件也可以快速求得其最优解。可以为实际生产生活解决问题带来极大地便利。

【关键词】流水线调度 线性整数规划模型 甘特图 LINGO

1问题重述

21世纪是一个注重效率和时间利用率的时代，在工业生产和经济发展中，我们竭尽全力去节省时间，在有限的时间内尽可能多的创造财富。所以，根据实际的生产需要及生产要求合理的安排生产的顺序尤为重要。

生产调度即将分好批的生产任务落实到加工设备上，以使某代价最小，所谓的某代价最小也即优化目标。所谓的流水线车间调度即有一组功能不同的机床，待加工的零件包含多道工序，每道工序在一台机床上加工，所有零件的加工顺序相同。

在本问题中，共有3个机床，6种待加工零件，每种零件需要经过3道工序，每台机床同一时间只能加工一种工件，确定了开始时的加工顺序随后的加工顺序不会改变。

建立适当的数学模型，确定加工件的先后顺序，使得加工所有用件用时最短。 6种工件加工工序需时（分钟）见下表1： 表1：6种加工工件各工序耗时表（min）

加工件 1 2 3 4 5 6 弯折 焊接 装配 3 6 3 5 5 7 5 4 2 4 4 5 5 2 4 6 3 6 2问题分析与假设

2.1问题分析

此问题属于规划问题，目的是给出使加工时间最短的工件加工顺序。 已知每个加工件在各个加工工序所需要的时间，并且规定每台机器每次只能处理一个加工件，每个加工件按照给定处理步骤即弯折——焊接——装配依次进行，要求出加工所有工件所用的最短时间。要让总的加工时间最短，每种机器工作时间是连续的，即中途不允许在有生产任务有做相应任务的机器空闲时，机器不加工。总的时间就是第一台机器开始工作到第三台机器停止工作的时间。 通过分析知道此问题是一个整数规划问题，准确的说是一个线性规划中的二次分配问题。根据题目要求忽略次要影响因素，将主要因素翻译成数学语言，利用已有的数学知识，建立相应的模型。忽略了机器加工的准备时间以及机器可能出现故障等突发条件，以工件加工顺序随初始顺序而确定，各工件按一定顺序加工为主要约束条件，建立使得加工总用时最少的整数规划模型。

2.2模型假设

(1) 机器正常工作，不出现故障,中途也不需要进行维护；

(2)机器加工效率不随时间改变，即加工件的先后顺序不影响各个工序的用

时； (3) 每种金属管件都要经过三个阶段即弯折、焊接、装配，先后顺序不允许

打乱， 两工序之间可以等一段时间也可以不隔时间；

(4)每种机器每次只能处理一个加工件，等待下一台机器处理时，按原顺序进

行不允许排在后面的加工件“插队”； （5） 所有机器准备时间（忽略）为零，即所有生产件立即进入加工； （6） 无紧急件及其他突发情况。

3符号说明

符号 含义 工件总数 加工工序数 第I个加工的工件第J道工序所需要的时间 第I个加工的工件开始第J道工序的时刻 i号加工件在第j个工序需要的时间 w： p wtIJ wbIJ tij bij i号加工件开始第j道工序的时刻 Yik 引入的0—1变量，Yik=??0，i号工件在k号工件前加工?1，i号工件在k号工件后加工 T 总用时 ?加工第j道工序的机器的时间利用效率 ?j 4模型一的建立与求解

4.1模型一的建立

此问题明显是根据生产顺序的排列组合，求最小的生产时间的问题。一共有六个工件共有720种可能的排列顺序。构建一个6?6的0-1矩阵，每行每列仅有一个元素为1，其余元素为0，共有720种矩阵。我们假设最优的方案已经找到，即第I个生产的工件工件号为i。

要求最小的加工时间，即第一台机器开始工作到最后一台机器停止工作的时间最短。转化为最后一个加工的工件开始第三道工序的时刻与第三道工序耗时之和即

T?wt63?wb63

（4.1）

又由假设可知每个工件依次经过弯折—焊接—装配，所以对于第I个加工的工件前一个工序的结束时间必须在不晚于下一道工序的开始时间即

wtIJ?wbIJ?wtI(J?1)

（4.2）

又每个机器每次只能加工一个工件故

第I+1个工件必须在第I个工件的J工序完成后才能进行J工序

wtIJ?wbIJ?wt(I?1)J，

（4.3）

因为已经假设最优的方案已经找到，wtIJ是对应最优方案的工序加工耗时，必须对原来的按工件序号组成的耗时矩阵变换为按加工顺序组成的耗时矩阵。引入6?6的0-1矩阵，每行每列仅有一个元素为1，其余元素为0。

?y11,y12,y13,y14,y15,y16??t11,t12,t13??wt11,wt12,wt13??y,y,y,y,y,y??t,t,t??wt,wt,wt?23??212223242526??212223??2122?y31,y32,y33,y34,y35,y36??t31,t32,t33??wt31,wt32,wt33???????? y,y,y,y,y,yt,t,twt,wt,wt43??414243444546??414243??4142?y,y,y,y,y,y??t,t,t??wt,wt,wt??515253545556??515253??515253???y61,y62,y63,y64,y65,y66????t61,t62,t63????wt61,wt62,wt63???ym?166mn?1,n?1,2,3,4,5,6

?yn?1mn?1,m?1,2,3,4,5,6两矩阵相乘得到的新矩阵，例如

wt11?y11?t11?y12?t21?y13?t31?y14?t41?y15?t51?y16?t61，

若最优解对应的y13?1，说明工件3排在第一个加工。第一行即第一个加工工件各加工工序的耗时，以此类推第6行是第6个加工工件各工序的耗时。综上，得到整数规划模型如下：

minwt63?wb63；

????y11,y12,y13,y14,y15,y16??t11,t12,t13??wt11,wt12,wt13???y21,y22,y23,y24,y25,y26??t21,t22,t23??wt21,wt22,wt23??????????y31,y32,y33,y34,y35,y36??t31,t32,t33??wt31,wt32,wt33???y,y,y,y,y,y??t,t,t???wt,wt,wt???414243444546??414243??414243???y51,y52,y53,y54,y55,y56??t51,t52,t53??wt51,wt52,wt53?????????y61,y62,y63,y64,y65,y66????t61,t62,t63????wt61,wt62,wt63?????6s..t???ymn?1,n?1,2,3,4,5,6?m?1?6??ymn?1,m?1,2,3,4,5,6?n?1?wtIJ?wbIJ?wbI(J?1)??wtIJ?wbIJ?wb(I?1)J?I=1,2,3,4,5,6? ??J=1,2,3注：为了表达简便，在约束条件中，将I取到6，J取到3，但wbI(J?1)在为3时越界，wb(I?1)J在I为6时越界，此时只需在编程的过程中对分IJ分别约束即可。 4.2模型的求解

将目标函数及约束条件输入到Lingo中运行求解，可以得到结果（程序语句

以及输出结果参见附录），可得加工顺序为为3—4—1—2—5—6。

为了更清晰的说明生产流程，由求解结果作出各工件开始、完成各工序的时间表4—1

7 模型的优化与模型改进

针对上述提出的不足之处，可进一步对模型进行优化，如：

1.对于模型1针对LINGO不能输出所有最优解得情况，在不了解其具体求解路径时，可以通过改变初始的工件各工序耗时矩阵，求得其它最优解。如3—1—6—5—4—2 ，

4—1—6—5—3—2，3—4—1—6—5—2，1—4—6—5—3—2都可以使总的加工时间为35min，提供了更多的可选择方案。

2.多种加工顺序均能达到时间最短的目标，但是不同的加工顺序对应各机器的时间利用效率不同，综合考虑增加加工成本最低的目标，建立多目标线性规划模型，求出更具有实际意义的加工顺序。

3.实际问题中，有可能多种安排顺序时间相差不大，这时根据每台机器运

转的成本不同，尽量使运转成本高的机器工作时间短，提高其时间利用效率。根据时间和成本所占不同权重，确定最优生产计划。

8模型的推广与应用

此类流水线生产调度优化问题在实际中经常碰到，增强和减弱约束条件后能运用到其他方面。例如安排人员面试顺序问题、将多项任务分配给多人完成、生产过程中存在制品库存问题、公交车的调度问题等都可建立类似的线性规划模型。将此模型稍作修改，具体问题具体分析便可以很好地解决这一类的优化排序，生产规划问题。运筹学的题目都可以用这类整数规划模型解决。故该模型具有一定的实用性与推广性。

参考文献

[1] 姜启源 谢金星 叶俊，《数学模型》（第三版），北京：高等教育出版社，2003。 [2] 湖北省大学生数学建模竞赛专家组，《数学建模》,武汉：华中科技大学出版

社。 [3] 韩中庚，《数学建模方法及其统计》，北京：高等教育出版社，2005。 [4] 罗万成，《大学生数学建模案例精选》，成都：西南交通大学出版社，2007。 [5] 何坚勇，《最优化方法》，北京：清华大学出版社，2007。 [6] 牛映武，《运筹学》，陕西：西安交通大学出版社，1994。 [7] 韩伯棠，《管理运筹学》，北京：电子工业出版社，2004。 [8] 张家琦，《决策分析》，北京：首都师范大学出版社，1998。 [9] 杨启凡，《数学建模竞赛》，杭州：浙江大学出版社，2005。

本文来源：https://www.bwwdw.com/article/v7ph.html