工方案,使在最短的时间内完成全部加工作业。对于每一个工件来说,它要在不同的机床上进行加工作业, 而且加工作业还要按一定的顺序进行:对每一个机床来说,它要加工不同的工件,而且必须按照一定的顺 序进行。虽然我们无论如何都可以求出工件的加工方案,但是,如果安排不当就必然会出现瓶颈现象 机床等待加工的时间较长。这样就会使得完成全部工件加工的总时间较长。由于工件加工作业之间具有优 先关系,有些作业必须等到其他作业完成后才可进行,这使得工件排序问题变得更加复杂。指派到机床上 的加工作业必须服从优先关系。 2.问题 假设用4台机床加2123个工件。各个工件的机床加工顺序,以及工件i在机床j上的加工时间(i=1, 2,3:j=1,2,3,4)如表10.3所示(单位:小时)。 10.3工件加工顺序及时间表 机床1→ 机床2→ 机床3 工件1 工件2 2 462 934 248 工件3 我们要找出一种工件加工作业方案使得完成全部工件加工的总时间达到最小。 3.模型 模型10.1.4—1:工件排序模型 ORDER 4.集合 我们定义三个基本集合一— GONGJ(工件)、 JICHUANG(机床)和 SHUIAN(时间)。我们用这三个 基本集合产生两个派生集合。一个是LNKS,它是一个密集,是由集合 GONGJ与 JICHUANG相乘而得 利用 LINKS我们产生两个属性,属性A存储工件在每个机床上加工所用时间:属性Y是控制变量。另 个派生集合是 GONGSHI,它也是一个密集,是由集合 GONGJ和SHAN相乘而得。利用 GONGSH我 们产生一个属性x,它表示工件在各个机床上加工的开始时间和结束时间。 5.变量 模型里的决策变量是属性X。X(i,1)、X(i,3)、X(i,5)、X(i,7)表示工件i在4个机床上的 加工开始时间,X(i,2)、X(i,4)、X(i,6)、X(i,8)表示工件i在4个机床上的加工结束时间(i=1, 2,3);当j是奇数时,Ⅹ(1,j、X(2,j)、Ⅹ(3,j)表示机床(j+1)/2加工3个工件的开始时间; 当j是偶数时,Ⅹ(1,j)、X(2,j)、X(3,j)表示机床j/2加工3个工件的结束时间(j=1,2,…8) 所有的(i,j)就构成了工件的加工时间表。属性Y是控制变量,只取0/1两个值,用来控制机床加工 工件的顺序 6.数据 在此模型中,输入的数据是存放在文件工件排序xls里的‘加工时间’域上。具体内容见表104中的 数据部分。 将数据放在模型之外可以使得模型的调试变得很容易。如果加工时间有变化,只要改动表104中的数 据,模型不需做任何改动就可获得相应的解答 输入数据是用下面的公式完成: A=@OLE(\ingo\工件排序xls’,’加工时间’); 7.目标函数 这个模型的目标很简单,它就是求出加工完全部工件的总时间的最小值。可用下式给出 @for(GONGJ (i): W>=x(i, m+3)ta (i, m)): 这里,m表示最后一个机床。 8.约束 在这个模型里,我们有下面两类约束 (1)每个工件加工次序的约束 对于每个工件来说,加工次序必须得到满足。即工件i(i=1,2,3)在某个机床上的开始加工时间加
工方案，使在最短的时间内完成全部加工作业。对于每一个工件来说，它要在不同的机床上进行加工作业， 而且加工作业还要按一定的顺序进行；对每一个机床来说，它要加工不同的工件，而且必须按照一定的顺 序进行。虽然我们无论如何都可以求出工件的加工方案，但是，如果安排不当就必然会出现瓶颈现象—— 机床等待加工的时间较长。这样就会使得完成全部工件加工的总时间较长。由于工件加工作业之间具有优 先关系，有些作业必须等到其他作业完成后才可进行，这使得工件排序问题变得更加复杂。指派到机床上 的加工作业必须服从优先关系。 2. 问题 假设用 4 台机床加 212 3 个工件。各个工件的机床加工顺序，以及工件 i 在机床 j 上的加工时间（i=1， 2，3；j=1，2，3，4）如表 10.3 所示（单位：小时）。 10.3 工件加工顺序及时间表 机床l→ 机床2→ 机床3→ 机床4 工件1 3 4 9 2 工件2 2 6 3 4 工件3 1 2 4 8 我们要找出一种工件加工作业方案使得完成全部工件加工的总时间达到最小。 3. 模型 模型 10.1.4—1：工件排序模型 ORDER 4. 集合 我们定义三个基本集合——GONGJ（工件）、JICHUANG（机床）和 SHUIAN（时间）。我们用这三个 基本集合产生两个派生集合。一个是 LINKS，它是一个密集，是由集合 GONGJ 与 JICHUANG 相乘而得。 利用 LINKS 我们产生两个属性，属性 A 存储工件在每个机床上加工所用时间；属性 Y 是控制变量。另一 个派生集合是 GONGSHI，它也是一个密集，是由集合 GONGJ 和 SHIJIAN 相乘而得。利用 GONGSHI 我 们产生一个属性 x，它表示工件在各个机床上加工的开始时间和结束时间。 5. 变量 模型里的决策变量是属性 X。X（i，1）、X（i，3）、X（i，5）、X（i，7）表示工件 i 在 4 个机床上的 加工开始时间，X（i，2）、X（i，4）、X（i，6）、X（i，8）表示工件 i 在 4 个机床上的加工结束时间（i=1， 2，3）；当 j 是奇数时，X（1，j）、X（2，j）、X（3，j）表示机床（j+1）／2 加工 3 个工件的开始时间； 当 j 是偶数时，X（1，j）、X（2，j）、X（3，j）表示机床.j／2 加工 3 个工件的结束时间（j=1，2，…8）。 所有的 X（i，j）就构成了工件的加工时间表。属性 Y 是控制变量，只取 0／1 两个值，用来控制机床加工 工件的顺序。 6. 数据 在此模型中，输入的数据是存放在文件工件排序.xls 里的‘加工时间’域上。具体内容见表 10.4 中的 数据部分。 将数据放在模型之外可以使得模型的调试变得很容易。如果加工时间有变化，只要改动表 10.4 中的数 据，模型不需做任何改动就可获得相应的解答。 输入数据是用下面的公式完成： A=@OLE（’＼lingo＼工件排序.xls’，’加工时间’）； 7. 目标函数 这个模型的目标很简单，它就是求出加工完全部工件的总时间的最小值。可用下式给出： min=W； @for（GONGJ（i）：W>=x（i，m+3）+a（i，m））； 这里，m 表示最后一个机床。 8. 约束 在这个模型里，我们有下面两类约束： （1）每个工件加工次序的约束 对于每个工件来说，加工次序必须得到满足。即工件 i（i=l，2，3）在某个机床上的开始加工时间加
上加工所用时间,必须小于等于在下一个机床上的开始加工时间。可以用下式表达: 复制过来 efor( LINKS(i’j)1j规t#m:x(i,纠一1)+a(蝎)<-x(i,2凇j1)): (2)每个机床加工次序的约束 对于每个机床来说,某一时刻只能加工一个工件。例如,我们只考虑工件1和工件2在机床1上的加 工情况,则必须满足:X(1,1)+a(1,1)≤X(2,1)或Ⅹ(2,1)+a(2,1)≤X(1,1)。我们可以 用下式表达机床加工次序的约束 复制过来? efor(GONGJ(k) Ik#1 bf S efor(UNKS(i’j)1i册防s-k+1 x(i,2巧1)+a(i,j)<=x(i+k,2q-1)+1000木y(i+k-1’j)); efor(GONGJ(k) Ik#1 bf s= efor( LINKS(i’j)Ii#1饼sk+1:t x(i+k,2木j一1)+a(i+k’j)<=x(i,2巧-1)+1000$(1-y(i+k-1j)) 限制y(i’j)为0-1变量 efor (GONGJ (i): @for (JICHUANG (j): @bin (y(i'j)))); 9.解答 模型求解后,我们将解答送回到文件工件排序.xls里的‘起止时间’域上。可用下式完成 eOLE(’\1ingo\工件排序.xls’,’起止时间’)=x 输出的具体结果如表10.4所示的数据部分。 表10.4工件加工时间表 机床1 机床2 机床3 机床4 开始时间结束时间开始时间结束时间开始时间|结束时间开始时间|结束时 工件1 工件2 9 12 19 工件30 15 10.2后勤保障模型 在这一节里,我们将开发两个后勤保障方面的模型。一个涉及工厂定位,一个涉及网络的最短线路 2.1 MODEL5: CAPLOC(工广定位模型) 1.背景 工厂定位模型是我们在第1章中介绍的有关运输问题的推广。工厂定位问题具有较大的决策范围,工 厂位置是变量。厂商很可能会遇到这样一类问题:在满足顾客对产品要求的前提下使总运输成本达到最少, 2.问题 某公司计划增加一些产品加工点(工厂),有三个位置可供选择。现有四个客户需要该公司的产品且 需要量已知。在每一个位置建立工厂都有与其关联的月运作费用,从工厂到客户的运输成本也不相同。此 外,工厂的运输能力也是有限的,不得突破它的生产能力。 现在需要决定哪些工厂要开工?开工的工厂给每一个客户运送多少产品使得总运输成本和工厂月运作费 用之和最少。 3.模型 模型10.2.1-1:工厂定位模型 CAPLOC 4.集合 在这个模型里,我们建立了两个基本集合:一个是 PLANT(工厂)集合:一个是 CUSTOMERS(客
上加工所用时间，必须小于等于在下一个机床上的开始加工时间。可以用下式表达： 复制过来 @for（LINKS（i'j）lj 规 t#m：x（i，纠一 1）+a（蝎）<--x（i，2 凇 j+1））； （2）每个机床加工次序的约束 对于每个机床来说，某一时刻只能加工一个工件。例如，我们只考虑工件 1 和工件 2 在机床 1 上的加 工情况，则必须满足：X（1，1）+a（1，1）≤X（2，1）或 X（2，1）+a（2，1）≤X（1，1）。我们可以 用下式表达机床加工次序的约束： 复制过来？？ @for（GONGJ（k）Ik#1 饼 s： @for（UNKS（i’j）li 册防 s—k+1： x（i，2 巧一 1）+a（i，j）<=x（i+k，2q 一 1）+1000 木 y（i+k 一 1'j）））； @for（GONGJ（k）Ik#1 饼 s= @for（LINKS（i'j）Ii#1 饼 s_k+1： t x（i+k，2 木 j 一 1）+a（i+k'j）<=x（i，2 巧一 1）+1000$（1 一 y（i+k 一 1'j））））； !限制 y（i’j）为 O 一 1 变量； @for（GONGJ（i）：@for（JICHUANG（j）：@bin（y（i'j））））； 9. 解答 模型求解后，我们将解答送回到文件工件排序.xls 里的‘起止时间’域上。可用下式完成： @OLE（’\1ingo＼工件排序.xls’，’起止时间’）=x 输出的具体结果如表 10.4 所示的数据部分。 表 10.4 工件加工时间表 机床 1 机床 2 机床 3 机床 4 开始时间 结束时间 开始时间 结束时间 开始时间 结束时间 开始时间 结束时间 工件l 3 6 9 13 13 22 22 24 工件2 l 3 3 9 9 12 15 19 工件3 O l 1 3 3 7 7 15 10.2 后勤保障模型 在这一节里，我们将开发两个后勤保障方面的模型。一个涉及工厂定位，一个涉及网络的最短线路。 lO.2.1 MODEL5：cAPLOC（工广定位模型） 1. 背景 工厂定位模型是我们在第 1 章中介绍的有关运输问题的推广。工厂定位问题具有较大的决策范围，工 厂位置是变量。厂商很可能会遇到这样一类问题：在满足顾客对产品要求的前提下使总运输成本达到最少。 2. 问题 某公司计划增加一些产品加工点（工厂），有三个位置可供选择。现有四个客户需要该公司的产品且 需要量已知。在每一个位置建立工厂都有与其关联的月运作费用，从工厂到客户的运输成本也不相同。此 外，工厂的运输能力也是有限的，不得突破它的生产能力。 现在需要决定哪些工厂要开工？开工的工厂给每一个客户运送多少产品使得总运输成本和工厂月运作费 用之和最少。 3. 模型 模型 10.2.1—1：工厂定位模型 CAPLOC 4. 集合 在这个模型里，我们建立了两个基本集合：一个是 PLANTS（工厂）集合；一个是 CUSTOMERS（客
户)集合。用这两个集合,我们建立了一个密集ARCS,它是由工厂集合与客户集合相乘而得。我们用个 集合来表达工厂与客户之间的运输线路 5.变量 在这个模型里,我们有两类决策变量。定义在集合ARCS上的属性VOL代表了工厂到客户每一个线 路上的运输量:定义在集合 PLANTS上的属性OPEN是用于表示哪些工厂将开工。具体地说,如果工厂 将开工,则OPEN(p)的值为L,否则为0。属性OPEN的元素将用下式定义为二元0/1变量 @FOR(PLANTS:@BIN(OPEN)); 6.目标函数 这个模型的目标函数是使得总成本(运输总成本加上运作成本的总和)达到最少。这可以用下面的表 达式计算: ITTL COSTIMIN=@SUM(ARCS: COST"VOL)+ @SUM (PLANTS: FCOST*OPEN) 目标函数里运输总成本是 aSUM(ARCS:COST*ⅤOL);而运作成本总和是aSUM( PLANTS FCOST*OPEN)。 7.约束 这个模型有两种类型的约束:第一种是每个客户必须得到足够的产品以满足需求:第二种是每个工厂 的运输量不能超过它的生产量 我们使用下面的表达式保证所有客户都可以获得足够的产品 @FOR(CUSTOMERS (J): [DEMAND] @SUM(PLANTS (I): VOL (I, J))>=DEM (J)): 对每一个客户,我们计算出了接收运输量的总和,并且让它大于或等于客户的需求量。为了限制工厂 的运输量不超过它的生产能力,我们使用下面的语句: @FOR(PLANTS (I): [SUPPLY] @SUM(CUSTOMERS (J): VOL(I,J))<= CAP(I)OPEN (I) ); 对于每一个客户,我们计算出了运输量的总和,并且让它小于或等于工厂的生产能力乘上表示工厂开 工与否的指示器OPEN 注意:为了使工厂可以运出产+品,在这些约束里的二元变量OPEN必须取1的值。 8.解答 求解模型,我们将得到下面的工厂定位模型的解答: Optimal solution found at step Objective valu 327.0000 Branch count Variable Value OPEN (PD) 1.000000 OPEN (P3) 1.000000 VOL (PI, C1) 15.00000 VOL (P1, C2) 17.00000 VOL (Pl, C4) 3.0000 VOL (P3, C3) 22.00000 VOL (P3, C4) 9.000000 我们让工厂1和工厂3。从工厂1开工,我们分别运出15,17和3个单位给客户1,2和4:从工厂3, 我们运出22个单位给客户3,运出9个单位给客户4 复制过来
户）集合。用这两个集合，我们建立了一个密集 ARCS，它是由工厂集合与客户集合相乘而得。我们用个 集合来表达工厂与客户之间的运输线路。 5. 变量 在这个模型里，我们有两类决策变量。定义在集合 ARCS 上的属性 VOL 代表了工厂到客户每一个线 路上的运输量；定义在集合 PLANTS 上的属性 OPEN 是用于表示哪些工厂将开工。具体地说，如果工厂 p 将开工，则 OPEN（p）的值为 l，否则为 0。属性 OPEN 的元素将用下式定义为二元 0／1 变量： @FOR（PLANTS：@BIN（OPEN））； 6. 目标函数 这个模型的目标函数是使得总成本（运输总成本加上运作成本的总和）达到最少。这可以用下面的表 达式计算： [TTL_COSTlMIN=@SUM(ARCS: COST*VOL)+ @SUM（PLANTS：FCOST*OPEN）； 目标函数里运输总成本是@SUM(ARCS: COST*VOL) ；而运作成本总和是@SUM（PLANTS： FCOST*OPEN）。 7. 约束 这个模型有两种类型的约束：第一种是每个客户必须得到足够的产品以满足需求；第二种是每个工厂 的运输量不能超过它的生产量。 我们使用下面的表达式保证所有客户都可以获得足够的产品： @FOR（CUSTOMERS（J）：[DEMAND] @SUM（PLANTS（I）：VOL（I，J））>=DEM（J））； 对每一个客户，我们计算出了接收运输量的总和，并且让它大于或等于客户的需求量。为了限制工厂 的运输量不超过它的生产能力，我们使用下面的语句： @FOR（PLANTS（I）：[SUPPLY] @SUM（CUSTOMERS（J）：VOL（I，J））<= CAP（I）{OPEN（I） ）； 对于每一个客户，我们计算出了运输量的总和，并且让它小于或等于工厂的生产能力乘上表示工厂开 工与否的指示器 OPEN。 注意：为了使工厂可以运出产+品，在这些约束里的二元变量 OPEN 必须取 1 的值。 8. 解答 求解模型，我们将得到下面的工厂定位模型的解答： Optimal solution found at step： 38 Objective value： 327.0000 Branch count： 3 Variable Value OPEN（P1） 1.000000 OPEN（P3） 1.000000 VOL（P1，C1） 15.00000 VOL（P1，C2） 17.00000 VOL（Pl，C4） 3.0000 VOL（P3，C3） 22.00000 VOL（P3，C4） 9.000000 我们让工厂 1 和工厂 3。从工厂 1 开工，我们分别运出 15，17 和 3 个单位给客户 l，2 和 4；从工厂 3， 我们运出 22 个单位给客户 3，运出 9 个单位给客户 4。 复制过来