9 3 4 5 7 11 10 图1 1 3 2 14 8 6 图2 12 13
(4) 模型求解
这是一个最优化问题，由于变量和约束条件都很多，人工求解有一定困难，因此可以借助lingo软件，求解得到最佳加工顺序和最少总完工时间。
在lingo软件中求解的部分代码：
MIN=5175-20*y1-28*y2-25*y3-16*y4-42*y5-12*y6-32*y7-10*y8-24*y9-20*y10-40*y11-24*y12-36*y13-16*y14=0;（目标函数的表示）。 由lingo计算得使得总完工时间最短的最佳加工次序为：
4?10?9?7?11?5?3?8?6?1?2?14?12?13，
此时总完工时间为2588。
5
2、机床花费总时间最优模型 (1)模型建立
机床花费总时间包括机床的总准备时间和总的工件加工时间。总的工件加工时间是一定的，因此解决机床花费总时间最短问题等价于机床准备总时间的最优化问题。本模型将此问题转化为图论中的遍历哈密顿链问题。构造图如下
9 3 4 5 7 11 10 图3
1 3 8 2 14 12 13 6 图4
图中的顶点表示加工工件号，实线表示规定的加工先后顺序，如有向实线x49表示加工顺序应该是先加工了4号工件才能加工9号工件。有向虚线表示可以相邻加工的两个工件号，如虚线x59表示可以先加工5号工件，再紧接着加工9号
6
工件；x95表示可以先加工9号工件，再紧接着加工5号工件。有向弧的权用wij表示，wij表示从节点i(表示加工工件i)到节点j(表示加工工件j)的准备时间。 表示是否选取加工第i号工件后紧接着加工第j号工件这一xij—是0-1变量，路径。
?0，表示选取了从加工i号工件到加工j号工件的顺序
xij??，表示不选取从加工i号工件到加工j号工件的顺序
?1
现要求求得一种加工顺序，使得机床的总等待时间最短。转换为图论问题即是寻找一条最短路径，并满足如下要求：
① 该路径经过所有节点一次且仅一次，且无环，因此路径数目要比节点数目少1；
② 该路径经过工件i所代表的节点时，必须已经经过工件i的所有前置节点。
根据图1，与图2，3号工件必定是排在第7个序号上，13号工件必定排在最后一个加工序号上，同理，12号工件必定是倒数第二个被加工，14号工件必定是倒数第三个被加工。因此问题简化为找到图3、图4这两部分的最优加工顺序。建立模型为：
Min z???wijxij,?i,j?0,1...14?
i?1j?11414s.t.
?14??xij?1?j?0,1...14??i?1?14??xij?1?i?0,1...14? ?j?1?x??0,1??i,j?0,1...14??ij?1414???xij?13?i?1j?1(2) 模型求解 本模型用lingo求解： 对图一求解（代码见附录7.1）
7
求解结果为：4→7→11→10→9→5→3 所需机床花费总时间为45。 对图二求解（代码见附录7.2）：
求解结果为：3→8→6→2→1→14→12→13 所需机床花费总时间为69。 3、总补偿费最少模型
本问题主要研究如何给出一个加工顺序使得总补偿费最小。 (1) 目标函数分析
变量说明:xj 表示第j个工件的完工时间（包括等待与加工两个阶段）
j=1 2???14
u表示确定时限，题目中给的值为100
mj?1表示第j个工件的完工时间超过了确定时限u j=1 2???14 mj?0表示第j个工件的完工时间没有超过了确定时限u
j=1 2???14
wj表示第j个工件的补偿费率
根据题目要求，只有超过了确定时限的工件才需要支付补偿费用，由此可以得到目标函数为：MIN Z3??mjwj?xj?u? （1.1）
j?114(2) 约束条件分析
根据题目给出的表中可以得知各工件之间的关系（1.2），由此也可以得到各工件完工时间之间的关系（1.3）。由分析知道工件3的完工时间为199，工件14的完工时间为285，工件12的完工时间为309，工件13的完工时间为345，因此工件3以后完工的工件的完工时间都会超过确定时限u，则mj?1（j为工件3以后完工的工件号，包括工件3）；而不管安排怎样的加工顺序工件4的完工时间都不会超过u，则m4?0；对于工件5，它加工之前工件4、7、11、10必须完工，因此工件5的完工时间至少为108，也超过了确定时限u，则m5?1；对于工件7，它最多排在工件4、9、10的后面，因此它的完工时间最多为92，不超过u，则m7?0；对于工件9、10、11，它们可能超过也可能不超过确定时限，
8
这只能根据加工的顺序来得到m9、m10、m11的值。
工件的完工时间xj与工件的加工顺序yi之间的关系为（1.5），由问题一可知。 (3) 总补偿费最少模型的建立
基于上面的分析，以（1.1）为目标函数，以（1.2）、（1.3）、（1.4）、（1.5）为约束条件建立模型
14MIN Z3??mjwj?xj?u?
j?1y1-y3>=1 y2-y8>=1 y3-y5>=1 y3-y9>=1 y5-y10>=1 y5-y11>=1 y6-y8>=1 y7-y4>=1 y8-y3>=1
（1.2） y9-y4>=1 y11-y7>=1 y12-y14>=1 y13-y12>=1 y14-y1>=1 y14-y2>=1 y14-y6>=1
x1>=219 m1?1
x2-x8>=28 m2?1 x5<=174 m3?1
x9<=174 m4?0 x5-x10>=42 m5?1 x5-x11>=42 m6?1
x6-x8>=12 m7?0x7-x4>=32 m8?1
x8>=209 （1.3） m12?1 x9-x4>=24 m13?1x11-x7>=40 m14?1 x1<=269 x2<=269 x6<=269 9
（1.4）