最新流水线调度优化模型.docx

流水线调度优化模型--武大数模选拔题目：流水线车间调度优化模型【摘 要】通过对问题的分析，流水线车间调度问题可以归 结为一个整数规划问题，本论文中根据题目所给的条 件以及实际情况依次建立起两个模型在满足加工时 间最短的前提下，基于对问题约束条件不同的翻译得 到两个模型从而得到不同的生产顺序，为决策者提供 了更多的生产方案联系生产生活实际情况，放松加 工工件必须遵循相对顺序不变这一约束条件，提出模 型的改进方向模型一，根据题目要求即每个工件的加工顺序为 弯折——焊接——装配且每台机器每次只能处理一个 加工件构造一个每行每列只含一个 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% 90% 96.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，提供了更多的可选择方案。

联系 实际生产，根据各机器单位时间的工作成本不同，可 以建立多目标规划模型，既要使总的时间最短又要使 整个加工过程机器的总成本最低，同时实现时间和成 本的最优化可以为决策者提供更实用的生产工件加 工顺序规划文末简述了模型的推广与应用将此线性整数规划模型稍作修改就可以运 用到安排面试人员的面试顺序、单机调度最优化、公交车的调度等问题枚举 的思想可以用到一些小规模的排序问题中，利用优化软件也可以快速求得其最 优解可以为实际生产生活解决问题带来极大地便利关键词】流水线调度 线性整数规划模型 甘特图 LINGO1问题重述21 世纪是一个注重效率和时间利用率的时代，在工业生产和经济发展中， 我们竭尽全力去节省时间，在有限的时间内尽可能多的创造财富所以，根据 实际的生产需要及生产要求合理的安排生产的顺序尤为重要生产调度即将分好批的生产任务落实到加工设备上，以使某代价最小，所谓 的某代价最小也即优化目标所谓的流水线车间调度即有一组功能不同的机 床，待加工的零件包含多道工序，每道工序在一台机床上加工，所有零件的加 工顺序相同在本问题中，共有 3个机床，6 种待加工零件，每种零件需要经过 3 道工 序，每台机床同一时间只能加工一种工件，确定了开始时的加工顺序随后的加 工顺序不会改变。

建立适当的数学模型，确定加工件的先后顺序，使得加工所有用件用时最 短6种工件加工工序需时（分钟）见下表 1：表 1 ： 6 种加工工件各工序耗时表（ min ）2.1 问题分析此问题属于规划问题，目的是给出使加工时间最短的工件加工顺序已知每个加工件在各个加工工序所需要的时间，并且规定每台机器每次只 能处理一个加工件，每个加工件按照给定处理步骤即弯折——焊接——装配依 次进行，要求出加工所有工件所用的最短时间要让总的加工时间最短，每种 机器工作时间是连续的，即中途不允许在有生产任务有做相应任务的机器空闲 时，机器不加工总的时间就是第一台机器开始工作到第三台机器停止工作的 时间通过分析知道此问题是一个整数规划问题，准确的说是一个线性规划中的二 次分配问题根据题目要求忽略次要影响因素，将主要因素翻译成数学语言， 利用已有的数学知识，建立相应的模型忽略了机器加工的准备时间以及机器 可能出现故障等突发条件，以工件加工顺序随初始顺序而确定，各工件按一定 顺序加工为主要约束条件，建立使得加工总用时最少的整数规划模型 2.2模型假设(1) 机器正常工作，不出现故障,中途也不需要进行维护；(2) 机器加工效率不随时间改变，即加工件的先后顺序不影响各个工序的用时；(3) 每种金属管件都要经过三个阶段即弯折、焊接、装配，先后顺序不允许打乱，两工序之间可以等一段时间也可以不隔时间；(4) 每种机器每次只能处理一个加工件，等待下一台机器处理时，按原顺序进行不允许排在后面的加工件“插队”；5) 所有机器准备时间(忽略)为零，即所有生产件立即进入加工；6) 无紧急件及其他突发情况。

3符号说明符号含义工件总数加工工序数wtJ第I个加工的工件第J道工序所需要的时间wb ——j第I个加工的工件开始第J道工序的时刻i号加工件在第j个工序需要的时间 i号加工件开始第j道工序的时刻Yik引入的0—1变量，Y =ikJo, i号工件在k号工件前加工1, i号工件在k号工件后加工总用时 加工第j道工序的机器的时间利用效率4模型一的建立与求解4.1模型一的建立此问题明显是根据生产顺序的排列组合，求最小的生产时间的问题一共有 六个工件共有720种可能的排列顺序构建一个6x6的0-1矩阵，每行每列仅 有一个元素为1，其余元素为 0，共有 720种矩阵我们假设最优的方案已经找 到，即第I个生产的工件工件号为io要求最小的加工时间，即第一台机器开始工作到最后一台机器停止工作的时间最短转化为最后一个加工的工件开始第三道工序的时刻与第三道工序耗时 之和即T 二 wt + wb (4.1)63 63又由假设可知每个工件依次经过弯折—焊接—装配，所以对于第 I 个加工的工 件前一个工序的结束时间必须在不晚于下一道工序的开始时间即wt + wb < wt ( 4.2)IJ IJ I (J+l)又每个机器每次只能加工一个工件故第 I+1 个工件必须在第 I 个工件的 J 工序完成后才能进行 J 工序wt + wb < wt ， ( 4.3)IJ IJ (I+l)J因为已经假设最优的方案已经找到， wtIJ 是对应最优方案的工序加工耗时，必须对原来的按工件序号组成的耗时矩阵变换为按加工顺序组成的耗时矩阵。

引 入6x6的0-1矩阵，每行每列仅有一个元素为1,其余元素为0y ,y,y,y,y,y"t,tt" wt ,wt ,wt111213141516111213111213y ,y,y,y,y,yt,t,twt ,wt ,wt212223242526212223212223y ,y,y,y,y,yt,t,twt ,wt ,wt313233343536313233—313233y ,y,y,y,y,yt,t,twt ,wt ,wt414243444546414243414243y ,y,y,y,y,yt,t,twt ,wt ,wt515253545556515253515253_ y ,y,y,y,y,y _t,t,t _wt ,wt ,wt61 62 63 64 65 66 61 62 63 61 62 63艺 y = 1,n = 1,2,3,4,5,6mnm=1艺 y = 1,m = 1,2,3,4,5,6mnn=1两矩阵相乘得到的新矩阵，例如wt = y x t + y x t + y x t + y x t + y x t + y x t ,11 11 11 12 21 13 31 14 41 15 51 16 61若最优解对应的 y =1，说明工件 3排在第一个加工。

第一行即第一个加工工13件各加工工序的耗时，以此类推第 6行是第 6个加工工件各工序的耗时综 上，得到整数规划模型如下：min wt + wb ；t , t , t11 12 13t , t , t21 22 23t , t , t31 32 33t , t , t41 42 43t , t , t51 52 53t , t , t61 62 63wt , wt , wt11 12 13wt , wt , wt21 22 23wt , wt , wt31 32 33wt , wt , wt41 42 43wt , wt , wt51 52 53wt , wt , wt61 62 6363 63y , y , y , y , y , y11 12 13 14 15 16y , y , y , y , y , y21 22 23 24 25 26y , y , y , y , y , y31 32 33 34 35 36y , y , y , y , y , y41 42 43 44 45 46y , y , y , y , y , y51 52 53 54 55 56y , y , y , y , y , y61 62 63 64 65 66艺 y = 1,n = 1,2,3,4,5,6mnm=1艺 y = 1,m = 1,2,3,4,5,6 mnn=1wt + wb < wbij ij i( j+1)wt + wb < wbij ij (i+1)ji =1,2,3, 4,5,6j=1,2,3注：为了表达简便，在约束条件中，将I取到6, J取到3,但wb 在为3时i(j+1)越界，wb 在I为6时越界，此时只需在编程的过程中对分I J分别约束即 (i+1)j可。

4.2模型的求解将目标函数及约束条件输入到Lin go中运行求解，可以得到结果（程序语 句以及输出结果参见附录），可得加工顺序为为 3—4—1—2—5—6为了更清晰的说明生产流程，由求解结果作出各工件开始、完成各工序的时间 表 4 — 1表4—1 工件 i 开始及完成工序 J 的时间、生产工序J 。