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

1、题目：流水线车间调度优化模型【摘要】通过对问题的分析，流水线车间调度问题可以归结为一个整数规划问题，本 论文中根据题目所给的条件以及实际情况依次建立起两个模型。在满足加工时间最 短的前提下，基于对问题约束条件不同的翻译得到两个模型从而得到不同的生产顺 序，为决策者提供了更多的生产方案。联系生产生活实际情况，放松加工工件必须 遵循相对顺序不变这一约束条件，提出模型的改进方向。模型一，根据题目要求即每个工件的加工顺序为弯折一一焊接一一装配且每 台机器每次只能处理一个加工件。构造一个每行每列只含一个1其余元素为0的矩 阵，通过矩阵乘积实现对原来工件工序耗时的行变换，整个过程相当于遍历。建立 线性规划

2、模型，利用LINGO软件求解。结果为当加工顺序为413652 时，用时最短为35min，利用Excel作出甘特图使整个生产安排流程更加清晰，引 入时间利用率的概念即加工工件的时间占开启时间的百分比，得到在加工顺序为 413652时机器一（弯折）机器二（焊接）机器三（装配）的时间利用 率依次为100%，67.W，100%，从而可从机器负载评价加工过程。模型二，将每台机器每次只能处理一个加工件这一约束条件翻译为一旦开始 顺序确定，则后续工序仍按原顺序进行。引入01变量表示两工件生产顺序，建 立01规划模型，利用LINGO软件求解。结果为当加工顺序为136452 时，用时最短为35min。利用甘特图

3、对结果进行分析与检验，得到3台机器的时间 利用效率分别为100%90%963%，为决策者选择方案提供了更多的参考指标。讨论本文所建模型的优点和缺点，横向的对比两个模型。在工件数目相对较 多（在十这一数量级上）的情况下选择模型一求解，LINGO可以在短时间内给出答 案；在数据量较少的情况下运用模型二求解，因为它模型建立过程简单易懂，编程 容易。但是对于工件数目处于百个数量级时，两种模型均无法在短时间内得到答 案，需要建立新的模型，设计新的算法求解此类大规模排序问题。针对模型的部分缺点提出优化改进方案，改变初始工件加工各工序耗时矩 阵，即动态设立初始点以弥补LINGO软件只能输出一组最优解的局限，

4、得出当加工 顺序为 316542，416532，341652，146 532时也能使加工时间最短为35min，提供了更多的可选择方案。联系实际生 产，根据各机器单位时间的工作成本不同，可以建立多目标规划模型，既要使总的 时间最短又要使整个加工过程机器的总成本最低，同时实现时间和成本的最优化。 可以为决策者提供更实用的生产工件加工顺序规划。文末简述了模型的推广与应用。将此线性整数规划模型稍作修改就可以运用 到安排面试人员的面试顺序、单机调度最优化、公交车的调度等问题。枚举的思想 可以用到一些小规模的排序问题中，利用优化软件也可以快速求得其最优解。可以 为实际生产生活解决问题带来极大地便利。【关键

5、词】流水线调度线性整数规划模型甘特图 LINGO1问题重述21世纪是一个注重效率和时间利用率的时代，在工业生产和经济发展中，我 们竭尽全力去节省时间，在有限的时间内尽可能多的创造财富。所以，根据实际的 生产需要及生产要求合理的安排生产的顺序尤为重要。生产调度即将分好批的生产任务落实到加工设备上，以使某代价最小，所谓 的某代价最小也即优化目标。所谓的流水线车间调度即有一组功能不同的机床，待 加工的零件包含多道工序，每道工序在一台机床上加工，所有零件的加工顺序相 同。在本问题中，共有3个机床，6种待加工零件，每种零件需要经过3道工 序，每台机床同一时间只能加工一种工件，确定了开始时的加工顺序随后的

6、加工顺 序不会改变。建立适当的数学模型，确定加工件的先后顺序，使得加工所有用件用时最 短。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 62问题分析与假设2.1问题分析此问题属于规划问题，目的是给出使加工时间最短的工件加工顺序。已知每个加工件在各个加工工序所需要的时间，并且规定每台机器每次只能 处理一个加工件，每个加工件按照给定处理步骤即弯折焊接装配依次进行，要求出加工所有工件所用的最短时间。要让总的加工时间最短，每种机器工作 时间是连续的，即中途不允许在有

7、生产任务有做相应任务的机器空闲时，机器不加 工。总的时间就是第一台机器开始工作到第三台机器停止工作的时间。通过分析知道此问题是一个整数规划问题，准确的说是一个线性规划中的二 次分配问题。根据题目要求忽略次要影响因素，将主要因素翻译成数学语言，利用 已有的数学知识，建立相应的模型。忽略了机器加工的准备时间以及机器可能出现 故障等突发条件，以工件加工顺序随初始顺序而确定，各工件按一定顺序加工为主 要约束条件，建立使得加工总用时最少的整数规划模型。2.2模型假设机器正常工作，不出现故障，中途也不需要进行维护；机器加工效率不随时间改变，即加工件的先后顺序不影响各个工序的用 时；每种金属管件都要经过三个

8、阶段即弯折、焊接、装配，先后顺序不允 许打乱，两工序之间可以等一段时间也可以不隔时间；每种机器每次只能处理一个加工件，等待下一台机器处理时，按原顺序进 行不允许排在后面的加工件“插队”；所有机器准备时间(忽略)为零，即所有生产件立即进入加工；无紧急件及其他突发情况。3符号说明符号含义W：工件总数P加工工序数第I个加工的工件第J道工序所需要的时间第I个加工的工件开始第J道工序的时刻%*I号加工件在第j个工序需要的时间*号加工件开始第j道工序的时刻引入的01变量，0, i号工件在k号工件前加工1, j号工件在左号工件后加工T总用时%加工第./道工序的机器的时间利用效率4模型一的建立与求解4.1模型

9、一的建立此问题明显是根据生产顺序的排列组合，求最小的生产时间的问题。一共有 六个工件共有720种可能的排列顺序。构建一个6x6的0-1矩阵，每行每列仅有一个元素为1，其余元素为0，共有720种矩阵。我们 假设最优的方案已经找到，即第T个生产的工件工件号为i。要求最小的加工时间，即第一台机器开始工作到最后一台机器停止工作的时 间最短。转化为最后一个加工的工件开始第三道工序的时刻与第三道工序耗时之和 即7 =曜加十呼&（4.1）又由假设可知每个工件依次经过弯折一焊接一装配，所以对于第I个加工的 工件前一个工序的结束时间必须在不晚于下一道工序的开始时间即（4.2）又每个机器每次只能加工一个工件故第I

10、+1个工件必须在第I个工件的J工序完成后才能进行J工序，（4.3）因为已经假设最优的方案已经找到，讷v是对应最优方案的工序加工耗时，必须对原来的按工件序号组成的耗时矩阵变换为 按加工顺序组成的耗时矩阵。引入6x6的0-1矩阵，每行每列仅有一个元素为1，其余元素为0。41s23w,w 上，W4.G ，知*上3w%,上1，如,加WhW的,W知41，如，43WE矽W如A 1 ,农-A%w知w上J、y j却 _W，w为少队无，儿I，人，死一玲 I，凫 坤为、a* y? I，也，瑁，外、为， 丹I J-in 30少桐，贝3我46孔I，为我印盼为，珞）64，骂犬咿二1,茬二，2,3,4,，6献二I龙” 二

11、L钢=1，2,3,4,5,6 n-i两矩阵相乘得到的新矩阵，例如吧1 5+为叫1 +入孩4】+九叫】+% 购+尸任叫1若最优解对应的Jim = 1，说明工件3排在第一个加工。第一行即第一个加工工件各加工工序的耗时，以此 类推第6行是第6个加工工件各工序的耗时。综上，得到整数规划模型如下：min十 卵方皿,凹4l，七占3力1*光*外a y：4，j%两右Cii 顷，上叫I，w上w知的1，肉半为，M.4 *，地上1盘殄如叫3知Xll, Xl； ? A41 J 尸45，JsGj f J , 匕 4W或W如叫3.乌 1 1 y. * r JV r Pis，Mfiy,l，y&2，63，- Jtri，比S

12、七1 棚妃七wi，wb，wL6k/，W4,5,6JM-I力 j,二 1,珀= 1,2,3,4,5,6 心洲打+岫与皿川）1=1,2,345,6J I.,%3注：为了表达简便，在约束条件中，将I取到6，J取到3,但也内）在为3时越界，讨川为6时越界，此时只需在编程的过程中对分IJ分别约束即可。4.2模型的求解将目标函数及约束条件输入到Lingo中运行求解，可以得到结果（程序语句 以及输出结果参见附录），可得加工顺序为为341256。为了更清晰的说明生产流程，由求解结果作出各工件开始、完成各工序的时 间表41表41工件i开始及完成工序J的时间生产工序J工件号F开始1（弯折）完成弯折开始2（焊接）完

13、成焊接开始3 （装配）装配完成4055991515891415203811171920246111819242430518232529303322329293333354.3模型检验与分析根据表41利用Excel作出甘特图如图4 一 1图4 一 1工件生产顺序甘特图即加工顺序为413652时，最短加工时间为35min。负责弯折的机器029min 一直工作，未出现空载情况;负责焊接的机器59min、1724min、2533min工作，从开始到停止共9min空载;负责装配的机器935min 一直工作。利用率二F品皿妇。%机器1（负责弯折）机器2 （负责焊接）机器3（负责装配）在一个生产周期时间利用

14、率忙 100%仍=普灯0()%=67.9%垫= 100%可以看出此加工顺序使三个机器的空载时间不均衡，机器二空载时间过长。此模型模拟遍历的过程，没有对工件不允许插队进行限制，而且各机器的时间利用效率不均衡，为了求解出更加合理的生产顺序，建立模型二。5模型二的建立与求解5.1模型的建立模型一采取遍历的思想方法来表示工件之间的绝对加工顺序，还有一种方法 就是对两个工件的加工顺序依次进行比较，引入01变量来表示任意两个工件的 相对加工顺序，根据他们相对的加工顺序求得总的加工顺序。首先每个工件都要满足按照弯折一焊接一装配的工序生产。即前一个工序结 束后才能进行后一个工序。故%十，垢f（5.1）其次工件

15、之间的加工顺序不改变，引入01变量，F = JO, i号工件在&号T件前加工“一 h珂工件在比号工件后加:：，若按一种工件3道工序全部加工完成，另一工件才开始加工，完成6种工件 需要94,故+在k之前加工时，（与+匕_如京94 叫=0（5.2）k之后加工时，0 W)件(i)=()(5.3)由(5.2)(5.3)得4+4-施亡94季匕%+虹_ 屈M9S(1一孔)(5.4)表示i号工件有可能在号厂件后加.，也有可能在它之前加工。对于任何一个工件，其加工结束的时间应不超过总时间，即妇+可3 - T(5.5)综上所述，得到一个以加工时间最短为目标的整数规划模型min Ts.t.妇4电可I与 + r F

16、 94* 孔站+%-岛 94* (1-V 加 *4 4 T 1,2,345,6& =1,2,3心6 j = 口35.2模型的求解将目标函数及约束条件输入到Lingol 1中运行求解，可以得到结果（程序语 句以及输出结果参见附录），即加工顺序为136452时加工时间最短为 35min。根据结果做出号工件开始第j道工序和完成第j道工序的时刻表51表51号工件开始第j道工序和完成第j道工序的时刻生产工序工件号1（弯折）完成弯折2（焊接）完成焊接3 （装配）装配完成103388132232929333335336810131741318182224305182323273033661313181824

17、5.3模型的检验与分析为了更加直观的表示整个生产流程，画出甘特图。如图5-2从甘特图中可以清晰的看出加工顺序为136452，总时间为 35min。工序1即弯折的条形图，负责弯折的机器从0-29min 一直工作，没有出现空 载情况;工序2的条形图，负责焊接的机器3-10min 工作，10-13min空载，13-33min 工作;工序3的条形图，负责装配的机器从8-17min 工作，17-18min空载，18- 35min工作。机器1（负责弯折）机器2 （负责焊接）机器3 （负责装配）在一个生 产周期时间利用率邛，X100% = 90% 33-3n. = 士 .lx 100% = 963%35-K

18、在此情况下，三个机器的利用率相差不大即机器负荷相对平衡。得到了比较 满意的生产顺序安排。6模型的评价本文建立了两个模型。模型一建立了线性整数规划模型，模拟遍历的过程， 解决了各生产工件任务量相等时完成任务的最短时间以及对应的加工顺序。模型二 引入01变量表示两工件相对加工顺序，建立了 01规划模型，求得使加工过程 最短的加工顺序。6.1模型的优点（1）采用较为成熟的数学理论建立模型，所建模型简单，通俗易懂。（2）为求得更为合理的生产工作调度表，建立多个模型，对结果进行比 较，有较强的实用性。（3）模型的计算采用LINGO软件，算法简便，编程实现简单；可信度较高， 便于推广。（4）甘特图的使用使

19、生产过程更加清晰，各机器工作时间，各工件加工进 度一目了然。（5）机器时间利用效率概念的引入从整体上评价了不同生产顺序的利弊。6.2模型的缺点（1）模型虽然综合考虑了很多因素，但为了建立模型，理想化了许多影响因 素，具有一定的局限性，得到的最优方案可能与实际有一定的出入。（2）模型只考虑了时间最短，没有考虑成本最低，有可能每个机器运转时单 位时间花费不同，模型结果与实际有一定差距。（3）所建立的模型对工件个数少的流水线调度比较适用，一旦工件种类增加 至100个及以上可能很难得到全局的最优解。（4）LINGO软件求解优化问题时，只能输出一组最优解，其他最优解不能输 出。即使得到了最短时间是35min，但是不能得到所有使与之对应的加工顺序。7模型的优化与模型改进针对上述提出的不足之处，可进一步对模型进行优化，如：对于模型1针对LINGO不能输出所有最优解得情况，在不了解其具体求解 路径时，可以通过改变初始的工件各工序耗时矩阵，求得其它最优解。如31一 6542，416532，341652，146532 都可以使总的加 工时间为35min，提供了更多的可