|
|
| |
|
| |
| |
| (两道工序的)工序问题(动态规划) |
|
[ 2008-9-4 19:49:00 | By: wantnon ] |
有n个零件x1,x2,...,xn通过两道工序A,B。同一时间每道工序上的零件数不得超过1个。已知各零件通过各工序所用的时间如下表：
现在问，如何安排零件的通过顺序才能使总通过时间最短？
1,转移方程：
从第一个零件输入A开始计时，最初B是空闲的，直到第一个零件通过A。
计时终止是在最后一个零件完全通过B。
当然，A在任何时刻都不会是空闲的（因为要想时间最短，必定上一个零件刚通过A，下一个零件马上被送入）。但是B可能会时而出现空闲（即当B口处理得太快，而A处理的零件接不上来），当然也可能出现积压（即当B口处理得太缓慢，A处理完的零件塞在B的入口）。
在B的非空闲时间里所有的零件都通过B，所以实际上我们有：
零件的总通过时间＝B的总空闲时间+b1+b2+...+bn
因此，要使零件的总通过时间最短，只需使B的总空闲时间最短。
易见，总耗时只是A口零件输入顺序的函数。(因为对于积压在B入口处且尚未输入B的那些零件，调换它们的次序对结果是完全没有影响的)。
但要注意"总耗时只与零件输入第一个口的顺序有关"这一结论对更多口的情况不成立－－例如有A,B,C三个口，由于BC可看作一个两个口中的系统，因此显然B口零件的输入顺序会影响零件通过BC的时间，进而影响到通过ABC的总耗时。所以总耗时不仅与A口零件输入顺序有关，也与B口的输入顺序有关(不过与C口输入顺序无关)。因此一般结论应该是：总耗时仅与前n-1个口的零件输入顺序有关。
因此可将每次从剩余零件中选取一个输入A口看作一个决策，从而转成多步决策问题。
如下划分阶段：从向A输入一个零件开始，至此零件通过A为止。
每个阶段都有许多可能状态，称为"状态群"，记第k阶段状态群为$S_k$。
用$(X_k,t_k)$描述$S_k$中的一个状态，其中：
$X_k$表示已通过A的零件集，
$t_k$表示B处理完当前其入口处的零件所需的时间。
用$J(X_k,t_k)$表示状态$(X_k,t_k)$时B工序的最小累积空闲时间。
考虑由$S_k$过渡到$S_{k+1}$：
对于$S_{k+1}$中每一个状态$(X_{k+1},t_{k+1})$,它可由$S_k$中不同状态施不同决策得到(当然也可能根本得不到)，为了得出最优的$J(X_{k+1},t_{k+1})$，需要考虑全面，即：
$J(X_{k+1},t_{k+1})=min_{Sub}(J(X_k,t_k)+max(a_i-t_k,0))$
其中$Sub={((X_k,t_k) in S_k),(i in I\\X_k),(b_i+max(t_k-a_i,0)=t_{k+1}),(X_kUi=X_{k+1}):}$
初值：
状态群$S_1$中:
J({x1},b1)=a1;
J({x2},b2)=a2;
...
J({xn},bn)=an;
最终目标：
得到最小的J(I,?)
也就是说当得到所有的J(I,?)之后，在其中选出最小的就是问题的最优解。
2：程序
(待)
|
|
| | |
|
