基于零件加工问题的0-1规划排序优化模型.docx

《基于零件加工问题的0-1规划排序优化模型.docx》由会员分享，可在线阅读，更多相关《基于零件加工问题的0-1规划排序优化模型.docx（23页珍藏版）》请在三一文库上搜索。

1、浙江师范大学数学建模竞赛培训：基于零件加工问题的0-1规划排序优化模型基于零件加工问题的0-1规划排序优化模型摘要零件加工排序问题为运筹学的排序问题，有各种不同的模型和不同的目标函数1。本文讨论的是零件加工流水作业(Flow-shop)排序排列问题，参考已有的零件加工4参量表 示法2,给出了添加上“限制”的5参量表示法：nE/mM/L(u)/P/f (nE零件数； mM 一机器数，L(u)一有无限制，f一目标函数)。对问题进行深入的分析、研究，建(1) 0-1规划排序时间优化模型： n目标函数：min1(ST1( ) +E (max( ST(),ST，)+ X： ),这里 ST( ) = ST

2、( )+X：). ni =2(2) 0-1规划排序价值优化模型：目标函数为：MaxZ ViYi,11(3)最长流程时间最短模型：fmsk =max*ms k, fmsk)+mtsk。siq 1。1q、运用lingo软件编程解决给出的10个零件的四个不完全相同机器台数、时间限制、目 标函数的问题：问题一，简单运用了 “ 0-1规划”模型部分，解答出了最优加工方案，其平均时 间为10.82小时，加工路线为3一5一1 一 10一7一4一2一8一9一6,此结果跟约翰逊算法 的结论相符合。问题二：在第一问得到的最优解的基础上，进行模型调整使得满足完工时间的限 制，最终得到了优化加工顺序及对应的零件在车间

3、停留的平均时间。问题三：由于全部零件都有完工时间的限制，因此不可能全部进行加工，采用“0-1规划”得出最大的工件价值。问题四：在问题一解的基础上，进行模型改进，得到零件加工的最大流程时间， 并用约翰逊法对结果进行验证。问题五：根据上述几个问题，运用“ 0-1规划”模型求出零件的车间停留平均时 问。并采用Gupta启发式算法对模型进行求解优化，得出最大流程时间。最后用约翰逊排序算法来检验并给出更一般化的简单解决排序问题的方法。模型提供了单双工序的0-1遍历计算，以及多工序下的启发式算法优化计算，满足不 同工序情况下的不同要求，追求最大程度的目标满足。关键词：零件加工0-1规划lingo 约翰逊法

4、Gupta启发式算法、问题重述零件加工问题某工厂的一个车间有一台高质量、高精度的机床，现有10种零件同时要求加工，这10种零件加工所需时间见附2表一所示。问题一：应按照怎样的顺序来安排10个零件的加工顺序，才能使这10个零件在车间 停留的平均时间最短？ ( 10E/1M /u/P/f(t)问题)问题二：如果部分零件有完工时间要求，完工时间如表一所示；应按照怎样的顺序来 安排10个零件的加工顺序，才能使这10个零件在车间停留的平均时间最短？(10E/1M /L/P/ f(t)问题)如果每个零件均有加工时间、完工时间和零件价值，见附2表二所示。问题三：建立模型求整个选择中，所选择零件加工的总价值最

5、大。(10E/1M /L/P/f(v)问题，并可以车间停留的平均时间最短为次要目标)如果这10种零件先在车床上车削，然后再在钻床上钻孔(AB两道工序)，加工所需 时间见附2表三所小。问题四：应按照怎样的顺序来安排10个零件的加工顺序，才能使这10个零件在车间 停留的平均时间最短？ ( 10E/2M /L/P/f(t)问题)问题五：建立数学模型，虑虑一般的n个零件在m台机器上加工排序问题。(nE/mM /u/P/ f (t)问题)、模型假设1、每个机器在同一时间只能加工一个零件。2、每个零件加工在上班时连续的，不中途不插入其它零件。3、忽略工件在转换工序时的运输时间。即每个零件在上道工序加工完毕

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

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

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

9、间，等待上一个零件加工完的时间（即从该零件在车床 加工完毕时刻起到其上一个零件在钻床上加工完毕这一段时间），该零件在钻床上加工的 时间。我们假设i零件在车床M1加工所需时间为X1i ,在钻床上M2加工所需时间为X2i ； i 零件完成在车床Mi加工的总时间为Me （i-1）零件完成在钻床M2加工的总时间为 M 2（i q ,（ i - 2 ） 0这里要分两种情况进行分析：1） .当Mii之M2（i）时，即i零件完成车床工序的总时间大于或等于（i-1）零件完成钻 工序的总时间，此时i零件不需要等待（i-1）零件而立即就进入钻工序，因此i零件完成 钻床工序的总时间表达式为 M 2i = M 1i

10、+ X2i ；2） .当Mu WM2（i）时，即i零件完成车工序的总时间小于或等于（i-1）零件完成钻工 序的总时间，此时i零件需要等待（i-1）零件完成钻床工序才能进入钻床加工。因此i零 件完成钻床工序的总时间表达式为 M2i = M2（iJ） + X2i o综合以上两种情况，得到i零件完成钻床工序的总时间计算公式为M 2i =Max ( M 1i , M 2(i)+ X 2i ( i a 1 )根据假设4,零件在车床上加工的顺序，和在钻床上加工的顺序一致。为了优化加工 时间：1、减少钻床等待时间，即在车床上加工时间越短的零件，加工顺序越靠前。2、充分利用加工前段的时间，即在钻床上加工时间越

11、长的零件，加工顺序越靠前。即约翰逊 法。问题五：考虑一般的n个零件在m台机器上加工排序问题，即nE/mM/u/P/f（t）问题。目标函数：（1）零件在车间停留的平均时间最短；（2） 最长流程时间最短。最长流程时间是从第一个工件在第一台机器开始加工时算起，到 最后一个工件在最后一台机器上完成加工时为止所经过的时间。假设开始加工的时间 为零，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最 长完工时间Cmaxo零件在车间停留的平均时间最短也就相当于零件在车间的总时间最 短。我们以10个零件在3台仪器上的加工为例。五、模型准备：（一）预备知识4参数表示法：n/m/A/B （其中

12、，n零件数；m机器数；A一车间类型，B 一目 标函数）。但对于一般情形，排列排序问题的最优解是相应的流水作业排序问题比较好的 解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应 流水作业排序问题的最优解。所以给出了假设 4来研究问题，同时这里的5参数表示法中的 A就换成了 P （排列排序车间类型）：5参数表示法：nE/mM/L（u）/P/f （ nE 零件数；mM 一机器数，L（u）一有无限 制，f一目标函数）（二）算法实现1、约翰逊法排序(1)在全部定额工时中找出tmin(2)若tmin在前工序，则该tmin对应的零件应尽量往前排；若tmin在后续工序，则对应

13、的零件往后排。(3)除去已经排了的零件，对余下零件继续按步骤(一)、(二)处理，直至全部排完。2、Gupta启发式算法Gupta 考虑了对于三台机器问题的Johnson规划的最优性这一有趣的问题。按照他的ti1 ：二 timot-d ti|1 im定义，零件i的斜度指标加定义为ei，1,ji =1,2，n ,其中 G =dmi ntj +ti,j由j11 g剪L然后，根据斜度指标排列零件的加工顺序。步骤如下： m(1)计算每个零件的总加工时间Ti =£ %，找出加工时间最长的零件J，将其作为关键 j 1零件。(2)对余下的零件,若tM <tm，则按匕不减的顺序排成一个序列Su,

14、若ti1 >tm,则按 tim不增的顺序排列成一个序列Sv。(3)顺序(Su, J, Sv)即为所求顺序。六、模型建立及求解(一)单工序模型及求解1、模型建立模型准备：先就问题五，引入0-1变量，表示在m个机器上n个零件的加工状况矩阵:f、XiiX12X1nPh =x21x22x2nma+a,xj =0或 1,h=1,2,3mxn1xn2xnn，模型建立：鉴于有两个目标：时间最短和价值最大。建立如下排序时间优化模型和排序价值优化 模型。排序时间优化模型：n i目标函数为： min m MTj.i3j U排序价值优化模型：10目标函数为：Max =£ ViY(在排序算法及程序中已

15、隐含有 Y)11MT1 =x11mti x12mt2 x1n mtn,MT2 ; x21mti x22mt2，- x2nmtn,MTn =xn1mit1 xn2mt2xnnmtn.限制约束1,每个顺序位最多只有一个工件：xI1 . x2 ., xn <1,x21 ' x22 '' x2n 一 1,xn1 - xn2 - xnn < 1.限制约束2:每个工件最多只排在一个顺序位上：。- x21 " - xn1 <1,x12 x22- xn2 < 1,xn x2n xnn < 1.完工时间限制：工MTiY < ftj (j=1,

16、2, n),若选择i工件加工，则记Y =1 ,否则 i 1记 Y =0 o2、计算实现陆吉健/1002673895 、赖兴俊、韩丹林-9 -2010.08.25开始定义需要的变量搜索n!种排序方 搜索出目标函数最小的排序第一步：定义所需变量，对排序前后加工、完工问，以及停留时间用相应的符号表示。第二步：用砧3水$："江门。16)；语句定义0/1变量，并 对其加以每个顺序位只能有一个零件每个零件只 能排在一个顺序位上的约束条件，实现 n!种排 序，检验每种排序是否符合时间约束条件。判断 出符合目标函数最小的最优排序。第三步：输入需要的原始数据各加工和完工时间，经程序 运行输出结果各零件

17、加工顺序和总停留时间。3.、问题一到三的求解问题一求解：没有时间限制（所以零件不存在冲突而不能排上），应用上述排序时间优化模型:目标函数为:i I0 imin （一 一 MTj）I0 y 7MT2 =X21mti x22 mt2X2iomtio,MTi =Ximti Xi2mt2Xiiomtio,MTio =Xioimti Xi02mt2Koiomti。.每个顺序位只能有一个工件：XiiX21'X12X110 = 1,' X22' X210 = 1,限制约束2:Xioi ' X102 '' Xioio = i.每个工件只能排在一个顺序位上：Xii

18、 X2iXioi = i,Xi2 X22Xi02 = i,X110 X210X1010lingo软件编程（详见附录1）,求解得：零件加工顺序平均 停留时间零件 编号35110742896所需 加工 时间1.21.61.81.922.42.733.14.110. 82（小时）作业 计划08:00 09:1209:12 10:4810:48 15:3615:36 08:3008:30 14:3014:30 16:5416:54 09:3614:36 16:3614:36 16:4209:42 14:480-1规划排序优化模型浙江师范大学数学建模竞赛培训：基于零件加工问题的表1问题二求解：基于问题一

19、，增加完工时间限制:则记Y =1,否则记Y =00Z MTiY < ftj （j =1,2,01 ,若选择 i 工件加工,i 1lingo软件编程（详见附录1）,求解得:零件加工顺序平均 停留时间零件 编号35291017648所需 加工 时间1.21.62.73.11.91.824.12.4312. 32（小时）作业 计划08:00 09:1209:12 10:4810:48 16:3016:30 10:3610:36 14:3014:30 16:1816:18 09:1809:18 16:2416:24 09:4809:48 14:48问题三求解：应用排序价值优化模型，结果如下：10

20、目标函数：MaX =£ MY（在排序算法及程序中已隐含有 丫）I 1MT2 =X21mt X22mt2X21°mt10,MT1 =X11mt1 X12mt2X11°mt10,MT10 =X101mt1 x102mt2Xo1omt10.限制约束1,每个顺序位只能有一个工件：X11X21，X12 一 一 X110 < 1, X22. X210 M1,X101 XI02X1010 - 1 限制约束2:每个工件只能排在一个顺序位上：X11 - X21X12X22x101 - 1,X102 一1,X110X210X1010 - 1 陆吉健/1002673895 、赖兴

21、俊、韩丹林-11 -2010.08.25浙江师范大学数学建模竞赛培训：基于零件加工问题的0-1规划排序优化模型完工时间限制：z MTiYi < ft j （j =1,2,，若选择i工件加工，则记Y =1,否则 i 1记 Y =0。lingo软件编程（详见附录1）,求解得：零件加工顺序零件 总价值零件 编号57861410所需 加工 时间1.6234.11.82.41.945.0作业 计划08:0009:3609:3614:3614:3608:3608:36 15:4215:4208:3008:30 10:5410:54 15:48（二）双工序模型及求解1、模型建立：根据问题分析，有模型如

22、下： 1 办 10目标函数：min (ST+£ 2印印？)+ Xi(2), 10y这里 ST(2) =ST +X1(2). , ST=£ MTi,ST=£ MTi(2)j 1jvMT1(1) =x11mti +x12mt2 + +x10mti10, .(1),1.1. 1MT2 =X21mt1 x22mt2 - 一X210mt10,(11MT10- X101mti.1X102mlt21 x1010 mti0,MT1(2) =X11mt12x12mt2, X110mt120,.(22MT2= x21 mt1.2X22mlt2X210mt20,MT102)=%瓶, X

23、102mt2%10 mti0限制约束1,每个顺序位只能有一个工件：X11X12X110 = 1,X21 ' X22 '' X210 =1,X101XI02X1010 = 1 .限制约束2:每个工件只能排在一个顺序位上:x11x21 ,' X101 = 1,X12X22' X102 - 1,X110 ' X210 ''X1010 - 1 .2、问题四求解：lingo软件编程（详见附录1）,求解得:零件加工顺序平均 停留时间 （小时）零件 编号36512710948车床 所需 加工 时间1.22.11.61.522.31.64.11.

24、73.0作业 计划08:00 09:1209:12 14:1814:18 15:5415:54 08:2408:24 10:2410:24 15:4215:42 08:1808:18 15:2415:24 08:0808:08 14:0812.91钻床 所需 加工 时间3.10.811.72.52.23.51.14.03.0作业 计划09:12 15:1815:18 16:0616:06 08:0608:24 10:0610:24 15:5415:54 09:0609:06 15:3615:36 16:4208:08 15:0815:08 09:08单位（小时）102030车床钻床钻床钻床钻床

25、开始工期 口完成(三)多工序模型及举例求解验证1、模型建立(1)零件在车间停留的平均时间最短目标函数:min (ST(m) +£ (max(STi(mA1,st(T) x?),这里 ST(m) =ST(m,)+X1(m). , ST(1)=£ MTi， j 1ST(m)八'MTi(m)j.(11.1.1MT1=x11mti x12mt2M：'x1nmtn,.d1.1.1MT2 =x21mti x22mt2x2nmtn, .(1),1.1, 1MTn =xnmt1 xn2mt2 -"nmtn, mmt- (m),m ,m ，,mMT1x11mtix1

26、2mt2,x x1n mtn,-(mmmmMT2x21 mtx22 mt2,x x2n mtn, mmt- (m), m ,m ,mMTn 二xn2 mt2"nnmlt .限制约束1,每个顺序位只能有一个工件：X21, Xn=1,x21x22十一,x2n=1,xn1-xn2,十一xnn=1.限制约束2:每个工件只能排在一个顺序位上：x11 - x21 - xn1 -1,%2 x22xn2 =1,x1n x2nxnn 1.(2)最长流程时|可最短设n个工件的加工顺序为S = Q,S2,，Sn,其中Si为排在第i位加工的工件的代号 以fmsik表示工件Si在机器M k上的完工时间，mtq

27、k表示工件Si在M k上的加工时间， i =1,2,，. ,n; k =1,2,，m ,则fm、k可按一下公式计算：叽1 二 1fms1k = fm1ki + mts1k,k=2, , ,m(1)fm*i= fmsik+ mtsik ,i=2, , ,n(2)fm0k=maxfm$&fm、k)+mtsik,i=2, , ,n, k=2, , ,m(3)最大流程时间为f (t)max = fm”(4)现在我们要对10个零件3台机器问题进行求解，要找出最优的加工顺序,先将其转换 成10种零件在两台设备上的加工排序约翰逊算法求解。排序步骤：判断min mt A >maxmtB w

28、63;min mtC至max mtB是否成立，倘若成立，便可进行以下步 骤。令 mt% =mtA. +mtB., mt = mtB. +mt? 式中： mtAj、mtBj、mt分别表示第j个 零件在A、B、C工序的定额工时。m&、ml分别表示第j个零件在假象工序 G H的定 额工时，G H分别为新的前工序和后工序。对mtGj、m%应用约翰逊法，得到优化排序。但是经过对比我们发现该加工排序不符合条件(一)，因此我们不能用上述方法，将 采用Gupta启发式算法。排序步骤如下：10计算每个工件的总加工时间ST=Z mtj ,找出加工时间最长的工件j ,将其作j 1为关键工作。对余下的工作，若

29、mi < mtim ,则按mt1不减的顺序排成一个序列su ,若mti1 > mtm ,则按mtim不增的顺序排列成一个序列Sv。顺序(Su, J, Sv)即为所求顺序。2、举例求解验证基于上述步骤，对10个零件3道工序，数据如下表5:M1M2M3112925973768489953236710479778894961310311图2进行求和可得：第四个零件在机器上加工的时间最大，因此把第四个零件作为关键工作。按步骤（2） （3）得出该批零件的最有加工顺序：1 一2一3一4一5一7一8一6 一9一 10。再根据matlab程序得出该批零件从开始加工到全部完工的时间为68个小时。J1

30、J2J3J4J5J7J8J6J910M11, 15,67,138,213,249,338,41，,486,543,57M22, 39,156,219,302,327,409,5010,601,611,62M39, 127,228,309,393,427,494,544,643,671,68经过排序之后，求解的最大流程时间 单位（小时）七、模型评价和推广1 、模型提供了单双工序的0-1遍历计算，以及多工序下的启发式算法优化计算，满 足不同工序情况下的不同要求，追求最大程度的目标满足。2、利用Lingo软件进行求解，实现了和Excel文件数据的输入输出，使得运算求解 更加便利，同时也便于推广使用。

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

32、的建立，南京工业职业技术学院学报（第二卷第三期），2002.95洪文 吴本忠，Lingo4.0 for windows最优化软件及应用，北京大学出版社，2001。附1 ： lingo程序程序一：解决问题一(10E/1M/u/P/f (t)问题)model:sets :gongjian/g1.g10/:shijian; !属性为：原始排序下，各零件加工时间；shunxu/s1.s10/:time,fin_time,number;!属性为：重新排序后，各零件加工时间、完成时间和对应原编号；links(shunxu,gongjian): note;endsets!目标函数：零件车间停留平均时间最小；

33、min=sumshunxu(I):fin_time(I)/10;!重新排序后，各零件而加工时间；for(shunxu(J):time(J)= sumgongjian(I):shijian(I)*note(I,J);!排序后，各零件的车间停留总时间；for(shunxu(I):fin_time(I)= su(shunxu(J)|J#le#I:time(J););!每个顺序位只能有二个零件；for(shunxu(I):su(gongjian(J): note(I,J)=1;);!每个零件只能排在一个顺序位上；for(gongjian(J):su(shunxu(I): note(I,J)=1;);!

34、将重新排放零件的编号赋值出来；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文档；OL(D:LJJG.xls?time','fin_time'尸time,number;!输入Excel文档原始排序下各零件的加工时间；shijian= OLED:LJJG.xls','shijian');enddataEnd程序二：解决问题二(10E/1M/

35、L/P/f (t)问题)model:sets :gongjian/g1.g10/:shijian,endtime;!属性为：原始排序下，各零件加工时间和限制时间；shunxu/s1.s10/:time,overtime,fin_time;!属性为重新排序后各个零件的机床加工时间，限制时间，完工时间；links(shunxu,gongjian): note;endsets!目标函数：零件车间停留平均时间最小；min=sumshunxu(I):fin_time(I)/10;!从新排序后各零件的机点口工时间(可能为零，即表示未选中零件)；for(shunxu(I):time(I)= sumgongj

36、ian(J):shijian(J)*note(I,J);!从新排序后各零件的完工时间(可能为零，即表示未选中零件)；for(shunxu(I):overtime(I)= su(gongjian(J):endtime(J)*note(I,J););!排序后各个零件的加工总时间；for(shunxu(I):fin_time(I)= sumshunxu(J)|J#le#I:time(J););!每个顺序位只能有一个零件或者没有零件；for(shunxu(I):su(gongjian(J): note(I,J)=1);!每个零件只能排在一个顺序位上；for(gongjian(J):sumshunxu(

37、I): note(I,J)=1);!各零件的完工时间约束；for(shunxu(I):sumshunxu(J)|J#le#I:time(J)<=overtime(I););!定义0/1变量；for(links: bin(note);data :!输出数据到Excel文档；OL(F:LJJG.xls','time2','fin_time2')=time,overtime;!输入Excel文档原始排序下各零件的加工时间；shijian= OLED:LJJG.xls','shijian');!输入Excel文档原始排序下各个零件的

38、完工时间；endtime= OLED:LJJG.xls','endtime');enddataend程序三：解决问题三(10E/1M/L/P/f (v)问题)model:!考虑完工时间和零件价值的排序问题；sets :gongjian/g1.g10/:shijian,endtime,gj_value;!属性为原始排序下，各个零件名的机床加工时间，完工时间，零件价值;shunxu/s1.s10/:time,overtime,fin_value;!属性为重新排序后，各个零件的机床加工时间，完工时间，零件价值;links(shunxu,gongjian): note;ends

39、ets!目标函数：所选零件总价值最大；max=sumshunxu(I):fin_value(I);!从新排序后，各零件的疝床加工时间(可能为零，即表示未选中零件) ；for(shunxu(I):time(I)= sumgongjian(J):shijian(J)*note(I,J);!从新排序后各，零件的完工时间(可能为零，即表示未选中零件) ；for(shunxu(I):overtime(I)= su(gongjian(J):endtime(J)*note(I,J););!从新排序后各，零件价值(可能为零，即表示未选中零件)；for(shunxu(I):fin_value(I)= su(go

40、ngjian(J):gj_value(J)*note(I,J););!每个顺序位只能有一个零件或者没有零件；for(shunxu(I):su(gongjian(J): note(I,J)<=1);!每个零件只能排在一个顺序位上；for(gongjian(J):su(shunxu(I): note(I,J)<=1);!各零件的完工时间约束；for(shunxu(I):sui(shunxu(J)|J#le#I:time(J)<=overtime(I);)；!定义0/1变量；for(links: bin(note);data :!输出数据到Excel文档；Ol(D:LJJG.xls

41、','time3','overtime3')=time,overtime;!输入Excel文档原始排序下，各零件的加工时间；shijian= OLD:LJJG.xls','shijian2');!输入Excel文档原始排序下，各零件的完工时间；endtime= OLED:LJJG.xls','endtime2');!输入Excel文档原始排序下，各零件的零件价值;gj_value= OLED:LJJG.xls','gj_value');enddataend程序四：解决问题四(10E/

42、2M /L/p/ f(t)问题)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!目标函数：零件车间停留平均时间最短；min=su(shunxu(I):zuan_fintime(I);!从新排序后各零件的车床加工时间；for(shunxu(I):che_time(I)= su(gongjian(J):che_shijian

43、(J)*note(I,J);)；!从新排序后各零件的钻床加工时间；for(shunxu(I):zuan_time(I)= su(gongjian(J):zuan_shijian(J)*note(I,J);)；!每个顺序位只能有一个零件；for(shunxu(I):su(gongjian(J): note(I,J)=1;)；!每个零件只能排在一个顺序位上；for(gongjian(J):su(shunxu(I): note(I,J)=1;);!从新排序后各零件在完成车工序的总时间；for(shunxu(I): che_fintime(I)= su(shunxu(J)|J#le#I:che_time(J);)；!从新排序后各零件在完成钻工序的总时间；for(shunxu(I)| I#gt#1:zuan_fintime(I)= if(che