基于零件加工问题的0-1规划排序优化模型(共20页)

1、精选优质文档-倾情为你奉上基于零件加工问题的0-1规划排序优化模型摘要零件加工排序问题为运筹学的排序问题，有各种不同的模型和不同的目标函数1。本文讨论的是零件加工流水作业(Flow-shop) 排序排列问题，参考已有的零件加工4参量表示法2，给出了添加上“限制”的5参量表示法：（零件数；机器数，有无限制，目标函数）。对问题进行深入的分析、研究，建立： （1）0-1规划排序时间优化模型：目标函数：，这里（2）0-1规划排序价值优化模型：目标函数为： （3）最长流程时间最短模型：=。运用lingo软件编程解决给出的10个零件的四个不完全相同机器台数、时间限制、目标函数的问题：问题一，简单运用了“0

2、-1规划”模型部分，解答出了最优加工方案，其平均时间为10.82小时，加工路线为35110742896，此结果跟约翰逊算法的结论相符合。 问题二：在第一问得到的最优解的基础上，进行模型调整使得满足完工时间的限制，最终得到了优化加工顺序及对应的零件在车间停留的平均时间。问题三：由于全部零件都有完工时间的限制，因此不可能全部进行加工，采用“0-1规划”得出最大的工件价值。问题四：在问题一解的基础上，进行模型改进，得到零件加工的最大流程时间，并用约翰逊法对结果进行验证。问题五：根据上述几个问题，运用“0-1规划”模型求出零件的车间停留平均时间。并采用Gupta启发式算法对模型进行求解优化，得出最大流

3、程时间。 最后用约翰逊排序算法来检验并给出更一般化的简单解决排序问题的方法。 模型提供了单双工序的0-1遍历计算，以及多工序下的启发式算法优化计算，满足不同工序情况下的不同要求，追求最大程度的目标满足。关键词：零件加工 0-1规划 lingo 约翰逊法 Gupta启发式算法1、 问题重述零件加工问题某工厂的一个车间有一台高质量、高精度的机床，现有10种零件同时要求加工，这10种零件加工所需时间见附2表一所示。问题一：应按照怎样的顺序来安排10个零件的加工顺序，才能使这10个零件在车间停留的平均时间最短？（问题）问题二：如果部分零件有完工时间要求，完工时间如表一所示；应按照怎样的顺序来安排10个

4、零件的加工顺序，才能使这10个零件在车间停留的平均时间最短？（问题）如果每个零件均有加工时间、完工时间和零件价值，见附2表二所示。问题三：建立模型求整个选择中，所选择零件加工的总价值最大。（问题，并可以车间停留的平均时间最短为次要目标）如果这10种零件先在车床上车削，然后再在钻床上钻孔（AB两道工序），加工所需时间见附2表三所示。问题四：应按照怎样的顺序来安排10个零件的加工顺序，才能使这10个零件在车间停留的平均时间最短？（问题）问题五：建立数学模型，虑虑一般的n个零件在m台机器上加工排序问题。（问题） 2、 模型假设1、每个机器在同一时间只能加工一个零件。2、每个零件加工在上班时连续的，不

5、中途不插入其它零件。3、忽略工件在转换工序时的运输时间。即每个零件在上道工序加工完毕之后，立即转移到下道工序继续加工。4、在多台机器上加工时，各零件在各机器上的加工顺序一致，且都需要加工，即问题为流水作业(Flow-shop) 排序排列问题。5、每个零件在每台机床上加工的时间为已知，且不受偶然事件的干扰。6、n个零件在m台机器上加工排序问题，不考虑零件完工时间限制，对应的目标函数为“短时间”（即最终完工时间最短）。7、作业计划，可安排的时间段为：上午08:0011:00，下午14:0017:00。3、 符号说明零件的加工时间零件的完工时间排序后，零件的加工时间零件的在车间的停留时间零件实际车间

6、停留时间机器（=1,2,3m） 注：其他符号，详见下文标注。4、 问题分析 无/有时限：问题一、四以及假设下的问题五，都是“无时限问题（即没有零件完工时间限制）”；而问题二、三，为“有时限问题”。单/多工序：问题一、二、三，为零件加工“单工序问题”；而问题四、五，为零件加工“多工序问题”。目标函数：问题一、二、四、五，追求的是“短时间（即零件车间平均停留时间最短）目标”（即目标函数）；问题三，追求的是“大价值（即所选择零件加工的总价值最大）目标”。追求零件车间平均停留时间最短意义在于使得零件总体价值能够争取到最大，特别是对于有着时间效应的零件。有时限问题，求解的前提，是要满足时间限制。然后结合

7、工序的多少，就这目标函数，求解最优的排序方案。问题一：问题，没有时间限制，所以零件不存在冲突而不能排上。问题二：问题，在问题一的基础上，4个零件出现完工时间的限制。问题三：问题，在问题一的基础上，10个零件都出现完工时间限制，同时目标函数转变为加工零件的总价值最大。由于每个零件都有完工时间的限制，零件之间的加工时间有可能冲突，因此，10种零件不一定都可以入选到最优加工序列中（即目标排序中可能出现零件空缺）问题四：根据总时间的定义，某零件从任务开始时刻起到完成钻床工序止所需要的总时间包括该零件完成车床工序的时间，等待上一个零件加工完的时间（即从该零件在车床加工完毕时刻起到其上一个零件在钻床上加工

8、完毕这一段时间），该零件在钻床上加工的时间。我们假设零件在车床加工所需时间为，在钻床上加工所需时间为；零件完成在车床加工的总时间为；（）零件完成在钻床加工的总时间为，（）。这里要分两种情况进行分析： 1).当时，即零件完成车床工序的总时间大于或等于（）零件完成钻工序的总时间，此时零件不需要等待（）零件而立即就进入钻工序，因此零件完成钻床工序的总时间表达式为=+; 2).当时，即零件完成车工序的总时间小于或等于（）零件完成钻工序的总时间，此时零件需要等待（）零件完成钻床工序才能进入钻床加工。因此零件完成钻床工序的总时间表达式为=+。 综合以上两种情况，得到零件完成钻床工序的总时间计算公式为 =M

9、ax（，）+ （） 根据假设4，零件在车床上加工的顺序，和在钻床上加工的顺序一致。为了优化加工时间：1、减少钻床等待时间，即在车床上加工时间越短的零件，加工顺序越靠前。2、充分利用加工前段的时间，即在钻床上加工时间越长的零件，加工顺序越靠前。即约翰逊法。 问题五：考虑一般的n个零件在m台机器上加工排序问题，即问题。目标函数：（1）零件在车间停留的平均时间最短；（2）最长流程时间最短。最长流程时间是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。假设开始加工的时间为零，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时

10、间。零件在车间停留的平均时间最短也就相当于零件在车间的总时间最短。我们以10个零件在3台仪器上的加工为例。五、模型准备：（一）预备知识4参数表示法：（其中，零件数；机器数；车间类型，目标函数）。但对于一般情形，排列排序问题的最优解是相应的流水作业排序问题比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。所以给出了假设4来研究问题，同时这里的5参数表示法中的就换成了（排列排序车间类型）：5参数表示法：（零件数；机器数，有无限制，目标函数）（2） 算法实现1、约翰逊法排序(1)在全部定额工时中找出。(2)若在前工序，则该对应的零件应尽

11、量往前排；若在后续工序，则对应的零件往后排。(3)除去已经排了的零件，对余下零件继续按步骤（一）、（二）处理，直至全部排完。2、Gupta启发式算法 Gupta考虑了对于三台机器问题的Johnson规划的最优性这一有趣的问题。按照他的定义，零件i的斜度指标定义为 ，其中。 然后，根据斜度指标排列零件的加工顺序。步骤如下：(1)计算每个零件的总加工时间，找出加工时间最长的零件J，将其作为关键零件。(2)对余下的零件，若，则按不减的顺序排成一个序列，若，则按不增的顺序排列成一个序列。(3)顺序（，J，）即为所求顺序。六、模型建立及求解（一）单工序模型及求解1、模型建立模型准备：先就问题五，引入0-

12、1变量，表示在个机器上个零件的加工状况矩阵：，模型建立：鉴于有两个目标：时间最短和价值最大。建立如下排序时间优化模型和排序价值优化模型。排序时间优化模型：目标函数为：排序价值优化模型：目标函数为： （在排序算法及程序中已隐含有） 限制约束1，每个顺序位最多只有一个工件： 限制约束2：每个工件最多只排在一个顺序位上：完工时间限制： (=1, 2, .) ，若选择工件加工,则记，否则记。2、计算实现开始第一步：定义需要的变量 定义所需变量，对排序前后加工、完工 间，以及停留时间用相应的符号表示。 第二步：是否搜索出目标函数最小的排序？搜索n！种排序方法 用for(links:bin(note);语

13、句定义0/1变量，并对其加以每个顺序位只能有一个零件每个零件只能排在一个顺序位上的约束条件，实现n！种排序，检验每种排序是否符合时间约束条件。判断出符合目标函数最小的最优排序。 第三步： 输入需要的原始数据各加工和完工时间，经程序运行输出结果各零件加工顺序和总停留时间。 输出结果结束3.、问题一到三的求解问题一求解： 没有时间限制（所以零件不存在冲突而不能排上），应用上述排序时间优化模型： 目标函数为： 限制约束1，每个顺序位只能有一个工件： 限制约束2：每个工件只能排在一个顺序位上：lingo软件编程（详见附录1），求解得：零件加工顺序平均停留时间零件编号35110742896所需加工时间1

14、.21.61.81.922.42.733.14.11082（小时）作业计划08:0009:1209:1210:4810:4815:3615:3608:3008:3014:3014:3016:5416:5409:3614:3616:3614:3616:4209:4214:48表1问题二求解：基于问题一，增加完工时间限制： (=1, 2, .10) ，若选择工件加工,则记，否则记。lingo软件编程（详见附录1），求解得：零件加工顺序平均停留时间零件编号35291017648所需加工时间1.21.62.73.11.91.824.12.431232（小时）作业计划08:0009:1209:1210:

15、4810:4816:3016:3010:3610:3614:3014:3016:1816:1809:1809:1816:2416:2409:4809:4814:48表2问题三求解：应用排序价值优化模型，结果如下：目标函数: （在排序算法及程序中已隐含有） 限制约束1，每个顺序位只能有一个工件： 限制约束2：每个工件只能排在一个顺序位上：完工时间限制： (=1, 2, .10) ，若选择工件加工,则记，否则记。lingo软件编程（详见附录1），求解得：零件加工顺序零件总价值零件编号57861410所需加工时间1.6234.11.82.41.945.0作业计划08:0009:3609:3614:3

16、614:3608:3608:3615:4215:4208:3008:3010:5410:5415:48表3（2） 双工序模型及求解1、模型建立： 根据问题分析，有模型如下： 目标函数： 这里 ，。 限制约束1，每个顺序位只能有一个工件： 限制约束2：每个工件只能排在一个顺序位上：2、问题四求解： lingo软件编程（详见附录1），求解得：零件加工顺序平均停留时间（小时）零件编号36512710948车床所需加工时间1.22.11.61.522.31.64.11.73.012.91作业计划08:0009:1209:1214:1814:1815:5415:5408:2408:2410:2410:2

17、415:4215:4208:1808:1815:2415:2408:0808:0814:08钻床所需加工时间3.10.811.72.52.23.51.14.03.0作业计划09:1215:1815:1816:0616:0608:0608:2410:0610:2415:5415:5409:0609:0615:3615:3616:4208:0815:0815:0809:08表4 单位（小时）图1（3） 多工序模型及举例求解验证1、模型建立 (1)零件在车间停留的平均时间最短 目标函数： 这里 ，。 限制约束1，每个顺序位只能有一个工件： 限制约束2：每个工件只能排在一个顺序位上：（2）最长流程时间

18、最短设个工件的加工顺序为，其中为排在第位加工的工件的代号。以表示工件在机器上的完工时间，表示工件在上的加工时间，则可按一下公式计算：= =+,k=2,m （1）=+ ,i=2,n （2）=,i=2,n, k=2,m （3）最大流程时间为 （4）现在我们要对10个零件3台机器问题进行求解，要找出最优的加工顺序, 先将其转换成10种零件在两台设备上的加工排序约翰逊算法求解。排序步骤:判断或是否成立，倘若成立，便可进行以下步骤。 令式中：、分别表示第个零件在A、B、C工序的定额工时。、分别表示第个零件在假象工序G、H的定额工时，G、H分别为新的前工序和后工序。 对、应用约翰逊法，得到优化排序。但是经

19、过对比我们发现该加工排序不符合条件（一），因此我们不能用上述方法，将采用Gupta启发式算法。排序步骤如下： 计算每个工件的总加工时间，找出加工时间最长的工件，将其作为关键工作。 对余下的工作，若，则按不减的顺序排成一个序列，若，则按不增的顺序排列成一个序列。 顺序（，J，）即为所求顺序。2、举例求解验证基于上述步骤，对10个零件3道工序，数据如下表5：M1M2M3112925973768489953236710479778894961310311表5进行求和可得：第四个零件在机器上加工的时间最大，因此把第四个零件作为关键工作。按步骤（2）（3）得出该批零件的最有加工顺序：1234578691

20、0。再根据matlab程序得出该批零件从开始加工到全部完工的时间为68个小时。J1J2J3J4J5J7J8J6J910M11, 15,67,138,213,249,338,417,486,543,57M22, 39,156,219,302,327,409,5010,601,611,62M39, 12 7,228,309,393,427,494,544,643,671,68经过排序之后，求解的最大流程时间单位（小时）图2七、模型评价和推广 1、模型提供了单双工序的0-1遍历计算，以及多工序下的启发式算法优化计算，满足不同工序情况下的不同要求，追求最大程度的目标满足。2、利用Lingo软件进行求解

21、，实现了和Excel文件数据的输入输出，使得运算求解更加便利，同时也便于推广使用。 3、由于在模型求解中利用了Lingo软件，大大简化了编程工作，且模型本身结合软件的使用就具有很强的可移植性，便于模型的推广。列如在推广到零件台机器的情况，只需在程序中的零件，顺序集里加入相应的属性；在程序段中加入对应的算法和约束条件就可以完全替换从而解决问题了。 八、参考文献1越民义，韩继业，排序问题中钓一些数学问题，数学的实践与认识，3(1976):59-70；4（1976），62-77。2 姜启源等，数学模型（第三版），高等教育出版社，2003。3 越民义、韩继业，n个零件在m台机床上的加工顺序，中国科学（

22、第五期），1975.94 高崚嶒、杨雨慧，关于零件加工排序问题数学模型的建立，南京工业职业技术学院学报（第二卷第三期），2002.95 洪文 吴本忠，Lingo4.0 for windows 最优化软件及应用，北京大学出版社，2001。附1：lingo程序程序一：解决问题一（问题）model:sets: gongjian/g1.g10/:shijian; !属性为：原始排序下，各零件加工时间; shunxu/s1.s10/:time,fin_time,number; !属性为：重新排序后，各零件加工时间、完成时间和对应原编号; links(shunxu,gongjian): note;ends

23、ets !目标函数：零件车间停留平均时间最小; min=sum(shunxu(I):fin_time(I)/10; !重新排序后，各零件的加工时间; for(shunxu(J):time(J)=sum(gongjian(I):shijian(I)*note(I,J); !排序后，各零件的车间停留总时间; for(shunxu(I):fin_time(I)=sum(shunxu(J)|J#le#I:time(J);); !每个顺序位只能有一个零件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每个零件只能排在一个顺序位上; for(gongj

24、ian(J): sum(shunxu(I): note(I,J)=1; ); !将重新排放零件的编号赋值出来;for(shunxu(J):number(J):for(if(note(I,J)=1,shunxu(J):number(J)=I,go);!有语法错误，未实现 !定义0/1变量; for(links:bin(note);data: !输出数据到Excel文档;OLE('D:LJJG.xls','time','fin_time')=time,number; !输入Excel文档原始排序下各零件的加工时间; shijian=OLE('

25、D:LJJG.xls','shijian');enddataEnd程序二：解决问题二（问题）model:sets: gongjian/g1.g10/:shijian,endtime; !属性为：原始排序下，各零件加工时间和限制时间; shunxu/s1.s10/:time,overtime,fin_time; ! 属性为重新排序后各个零件的机床加工时间，限制时间，完工时间; links(shunxu,gongjian): note;endsets !目标函数:零件车间停留平均时间最小; min=sum(shunxu(I):fin_time(I)/10;!从新排序后各零件

26、的机床加工时间（可能为零，即表示未选中零件）; for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!从新排序后各零件的完工时间（可能为零，即表示未选中零件）;for(shunxu(I): overtime(I)=sum(gongjian(J):endtime(J)*note(I,J); );!排序后各个零件的加工总时间; for(shunxu(I): fin_time(I)=sum(shunxu(J)|J#le#I:time(J); ); !每个顺序位只能有一个零件或者没有零件; for(shunxu(I): sum(gon

27、gjian(J): note(I,J)=1); !每个零件只能排在一个顺序位上; for(gongjian(J):sum(shunxu(I): note(I,J)=1); !各零件的完工时间约束; for(shunxu(I): sum(shunxu(J)|J#le#I:time(J)<=overtime(I); ); !定义0/1变量; for(links:bin(note);data: !输出数据到Excel文档;OLE('F:LJJG.xls','time2','fin_time2')=time,overtime; !输入Excel文档

28、原始排序下各零件的加工时间; shijian=OLE('D:LJJG.xls','shijian'); !输入Excel文档原始排序下各个零件的完工时间; endtime=OLE('D:LJJG.xls','endtime');enddataend程序三：解决问题三（问题）model: !考虑完工时间和零件价值的排序问题;sets: gongjian/g1.g10/:shijian,endtime,gj_value; ! 属性为原始排序下，各个零件名的机床加工时间，完工时间，零件价值; shunxu/s1.s10/:time,ov

29、ertime,fin_value; ! 属性为重新排序后，各个零件的机床加工时间，完工时间，零件价值; links(shunxu,gongjian): note;endsets !目标函数：所选零件总价值最大; max=sum(shunxu(I):fin_value(I);!从新排序后，各零件的机床加工时间（可能为零，即表示未选中零件）; for(shunxu(I): time(I)=sum(gongjian(J):shijian(J)*note(I,J);!从新排序后各，零件的完工时间（可能为零，即表示未选中零件）;for(shunxu(I): overtime(I)=sum(gongjia

30、n(J):endtime(J)*note(I,J); );!从新排序后各，零件价值（可能为零，即表示未选中零件）;for(shunxu(I): fin_value(I)=sum(gongjian(J):gj_value(J)*note(I,J); ); !每个顺序位只能有一个零件或者没有零件; for(shunxu(I): sum(gongjian(J): note(I,J)<=1); !每个零件只能排在一个顺序位上; for(gongjian(J):sum(shunxu(I): note(I,J)<=1); !各零件的完工时间约束; for(shunxu(I): sum(shun

31、xu(J)|J#le#I:time(J)<=overtime(I); ); !定义0/1变量; for(links:bin(note);data: !输出数据到Excel文档; OLE('D:LJJG.xls','time3','overtime3')=time,overtime; !输入Excel文档原始排序下，各零件的加工时间; shijian=OLE('D:LJJG.xls','shijian2'); !输入Excel文档原始排序下，各零件的完工时间; endtime=OLE('D:LJJG.x

32、ls','endtime2'); !输入Excel文档原始排序下，各零件的零件价值; gj_value=OLE('D:LJJG.xls','gj_value');enddataend程序四：解决问题四（问题）model: !零件先车后钻的排序问题;sets: gongjian/g1.g10/:che_shijian,zuan_shijian; shunxu/s1.s10/:che_time,zuan_time,che_fintime,zuan_fintime; links(shunxu,gongjian): note;endsets !目

33、标函数：零件车间停留平均时间最短; min=sum(shunxu(I):zuan_fintime(I);!从新排序后各零件的车床加工时间; for(shunxu(I): che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J); );!从新排序后各零件的钻床加工时间;for(shunxu(I): zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J); ); !每个顺序位只能有一个零件; for(shunxu(I): sum(gongjian(J): note(I,J)=1; ); !每个零件只能排在一个顺序位上; for(gongjian(J): sum(shunxu(I): note(I,J)=1; );!从新排序后各零件在完成车工序的总时间;for(shunxu(I): che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J); );!从新排序后各零件在完成钻工序的总时间;for(s