动态规划应用举例 - 图文(9)

现在，我们以在机床A上更换工件的时刻作为时段。以X表示在机床A上等待加工的按取定顺序排列的工件集合。以x表示不属于X的在A上最后加工完的工件。以t表示在A上加工完x的时刻算起到B上加工完x所需的时间。这样，在A上加工完一个工件之后，就有(X，t)与之对应。

选取(X，t)作为描述机床A、B在加工过程中的状态变量。这样选取状态变量，则当X包含有s个工件时，过程尚有s段，其时段数已隐含在状态变量之中，因而，指标最优值函数只依赖于状态而不明显依赖于时段数。

令f(X,t)为由状态(X，t)出发，对未加工的工件采取最优加工顺序后，将X中所有工件加工完所需时间。

f(X,t,i)为由状态(X，t)出发，在A上加工工件i后，对以后未加工的工件采取最优加工顺序后，将

X中所有工件加工完所需时间。

f(X,t,i,j)为由状态(X，t)出发，在A上相继加工工件i与j后，对以后加工的工件采取最优顺序后，

将X中的工件全部加工完所需要的时间。

不难得到 f(X,t,i)???ai?f(X/i,t?ai?bi) 当t?ai时?ai?f(X/i,bi) 当t?ai时

记zi(t)?max (t?ai,0)?bi，上式就可合并写成f(X,t,i)?ai?f?X/i,zi(t)? 其中X/i表示在集合X中去掉工件i后剩下的工件集合。

由定义，可得 f(X,t,i,j)?ai?aj?f ??X/?i,j?,zij(t)??

其中zij(t)是在机床A上从X出发相继加工工件i、j，并从它将j加工完的时刻算起，至在B上相继加工工件i、j并将工件加工完所需时间。故(X/?i,j?,zi j(t))是在A加工i、j后所形成的新状态。即在机床A上加工i、j后由状态(X，t)转移到状态(X/?i,j?,zi j(t))。

仿照zi(t)的定义，以X/?i,j?代替X/?i?，zi(t)代替t，aj代替ai，bj代替bi，则可得

zi j(t)?max??zi(t)?aj,0???bj

j故

zi j(t)?max?max(t?ai,0)?bi?aj,0??bjj?i??max?maxt?ai?aj?bi,bi?aj),0??bj j?i??max??t?ai?aj?bi?bj,bi?bj?aj,bj??i,j

将i、j对调，可得

f(X,t,j,i)?ai?aj?f??X/?i,j?,zji(t)??zj i(t)?max?t?ai?aj?bi?bj,bi?bj?ai,bi??i,j?

由于f(X,t)为t的单调上升函数，故当zi j(t)?zj i(t)时，有f(X,t,i,j)?f(X,t,j,i)

因此，不管t为何值，当zi j(t)?zj i(t)时，工件i放在工件j之前加工可以使总的加工时间短些。而由zi j(t)和zj i(t)的表示式可知，这只需要下面不等式成立就行。即

max (bi?bj?aj,bj)?max (bi?bj?ai,bi)

i,ji,j将上不等式两边同减去bi与bj，得max (?aj,?bi)?max (?ai,?bj)

i,ji,j即有 min(ai,bj)?min(aj,bi)

i,ji,j这个条件就是工件i应该排在工件j之前的条件。即对于从头到尾的最优排序而言，所有前后相邻接

的两个工件所组成的对，都必须满足上述不等式。根据这个条件，得到最优排序规则如下：

(1) 先给出工件加工时间的工时矩阵M???a1 a2?an??

?b1 b2?bn?(2) 在工时矩阵M中找出最小元素；若它在上行，则将相应的工件排在最前位置；若它在下行，则将相应的工件排在最后位置。

(3) 将排定位置的工件所对应的列从M中划掉，然后对余下的工件重复按(2)进行。但那时的最前位置(或最后位置)是在已排定位置的工件之后(或之前)。如此继续下去，直至把所有工件都排完为止。

例9 设有5个工件需在机床A、B上加工，加工的顺序是先A后B，每个工件所需加工时间(单位：小时)如表9-10所示。问如何安排加工顺序，使机床连续加工完所有工件的加工总时间最少?并求出总加工时间。

表9-10

加工时间 机床 工件号码 1 2 3 4 5 解 工件的加工工时矩阵为

A 3 7 4 5 7 B 6 2 7 3 4

?3M???6根据最优排序规则，故最优加工顺序为：

7247537? 4??1?3?5?4?2

总加工时间为28小时。

六、 设备更新问题

在工业和交通运输企业中，经常碰到设备陈旧或部分损坏需要更新的问题。从经济上来分析，一种设备应该用多少年后进行更新为最恰当，即更新的最佳策略应该如何，从而使在某一时间内的总收入达到最大(或总费用达到最小)。

现以一台机器为例，随着使用年限的增加，机器的使用效率降低，收入减少，维修费用增加。而且机器使用年限越长，它本身的价值就越小，因而更新时所需的净支出费用就愈多。设：

Ij(t)—— 在第j年机器役龄为t年的一台机器运行所得的收入。 Oj(t)—— 在第j年机器役龄为t年的一台机器运行时所需的运行费用。 Cj(t)—— 在第j年机器役龄为t年的一台机器更新时所需更新净费用。

?—— 折扣因子(0???1)，表示一年以后的单位收入的价值视为现年的?单位。

T —— 在第一年开始时，正在使用的机器的役龄。n —— 计划的年限总数。

gj(t)—— 在第j年开始使用一个役龄为t年的机器时，从第j年至第n年内的最佳收入。 xj(t)—— 给出gj(t)时，在第j年开始时的决策(保留或更新)。

为了写出递推关系式，先从两方面分析问题。若在第j年开始时购买了新机器，则从第j年至第n年得到的总收入应等于在第j年中由新机器获得的收入，减去在第j年中的运行费用，减去在第j年开始时役龄为t年的机器的更新净费用，加上在第j+1年开始使用役龄为1年的机器从第j+1年至第n年的最佳收入；若在第j年开始时继续使用役龄为t年的机器，则从第j年至第n年的总收入应等于在第j年由役龄为t年的机器得到的收入，减去在第j年中役龄为t年的机器的运行费用，加上在第j+1年开始使用役龄为t+1年的机器从第j+1年至第n年的最佳收入。然后，比较它们的大小，选取大的，并相应得出是更新还是保留的决策。

将上面的分析写成数学形式，即得递推关系式为：

?R:Ij(0)?Oj(0)?Cj(t)??gj?1(1)?gj(t)?max??K:I(t)?O(t)??g(t?1)??jjj?1??

(j?1,2,?,n ; t?1,2,?,j?1,j?T?1)其中“K”是Keep的缩写，表示保留使用；“R”是Replacement的缩写，表示更新机器。

由于研究的是今后n年的计划，故还要求gn?1(t)?0

例10 假设n?5,??1,T?1，其有关数据如表9-11所示。试制定5年中的设备更新策略，使在5年内的总收入达到最大。

表9-11

产品年序 机龄 项目 收入 运行费用 更新费用 第一年 0 1 2 3 4 0 第二年 1 2 3 第三年 0 1 2 第四年 第五年 0 1 0 32 4 34 期前 1 2 3 4 5 18 16 16 14 14 8 8 9 9 10 32 34 36 36 38 22 21 20 18 16 27 25 24 22 29 26 24 30 28 6 6 8 8 10 5 6 8 9 5 5 6 4 5 27 29 32 34 37 29 31 34 36 31 32 33 32 33