§6排序问题 设有n个不同零件A,A,., A,需要在m台不同机床B污 B2,,B。上加工，每个零件都必须依次经过B,B2,.,Bm 各道加王工序。 ·已知零件A在机床B上的加工时间(=12ni1,2.m),问 应如何确定各零件的加工顺序，使在第一台机床B上加工第 个零件开始到在第m台机床B.m上将最后一个零件加工完为止， 所用的总时间最少？这就是所谓的mxn同序加工的排序问题。 对于≥3的排序问题，目前尚无有效解法，而对于只有两个工 序，即m2的排序问题，可以用动态规战划方法加以解决。本节 我们就讨论它的解法。 ·设n个不同零件依次在机床A、B上加工，用a、b分别表示 零件在A、B上的加工时间。 ·n个零件在机床A上有个加工顺序，在机床B上也有个加工 顺序，不难证明，使得总工期最少的加工顺序，一定在A、B机 床上具有相同的加工顺序
§6 排序问题 • 设有n个不同零件A1，A2，…，An需要在m台不同机床B1， B2，…，Bm上加工，每个零件都必须依次经过B1，B2，…，Bm 各道加工工序。 • 已知零件Ai在机床Bj上的加工时间（i=1,2…n;j=1,2…m),问 应如何确定各零件的加工顺序，使在第一台机床B1上加工第一 个零件开始到在第m台机床Bm上将最后一个零件加工完为止， 所用的总时间最少？这就是所谓的m×n同序加工的排序问题。 对于m≥3的排序问题，目前尚无有效解法，而对于只有两个工 序，即m=2的排序问题，可以用动态规划方法加以解决。本节 我们就讨论它的解法。 • 设n个不同零件依次在机床A、B上加工，用ai、bj分别表示 零件i在A、B上的加工时间。 • n个零件在机床A上有个加工顺序，在机床B上也有个加工 顺序，不难证明，使得总工期最少的加工顺序，一定在A、B机 床上具有相同的加工顺序
·事实上，若顺序不样，在A上加工完的某零件不能马上在B 上加工，而要等到另个或一些零件在书上加工完后，才能加工， 这势必使B的等待加工时间加长，从而使总的加工时间延长。 当加工顺序取定后，在机床A上没有等待时间，而在机床B上 则常常等待。因此，寻找最优排序方案只有尽量减少在机床B上 等待加工的时间。 现在我们以在机床A上更换零件的时刻为阶段k=1,2,.n 以X表示在机床A上等待加工的零件集合：以x表示不属王X 的在A上加工的零件，以表示在A上加工完x时刻算起到B上加工 完x所需时间。这样在A上加工完一个零件后，就有(Xt)与之 对应，选取(X,)作为描述加工过程的状态变量。 令f(X,)表示由状态(Xt)出发，对未加工的零件采取最 优加工顺序后，将X中所有零件加工完所需的时间。 ·令f(Xt)表示由状态(X,t)出发，在A上先加正零件， 然后再对以后的零件采取最优加工顺序后，将X中所有零件加工 完所需的时间。注意，这时表示从零件1在A上加工完的时刻算 起直到在B上把它加工完所需的时间
• 事实上，若顺序不一样，在A上加工完的某零件不能马上在B 上加工，而要等到另一个或一些零件在B上加工完后，才能加工， 这势必使B的等待加工时间加长，从而使总的加工时间延长。 • 当加工顺序取定后，在机床A上没有等待时间，而在机床B上 则常常等待。因此，寻找最优排序方案只有尽量减少在机床B上 等待加工的时间。 • 现在我们以在机床A上更换零件的时刻为阶段 k=1，2,…n. • 以X表示在机床A上等待加工的零件集合；以x表示不属于X 的在A上加工的零件；以t表示在A上加工完x时刻算起到B上加工 完x所需时间。这样在A上加工完一个零件后，就有（X,t）与之 对应，选取（X,t）作为描述加工过程的状态变量。 • 令f（X,t）表示由状态（X,t）出发，对未加工的零件采取最 优加工顺序后，将X中所有零件加工完所需的时间。 • 令f（X,t,i）表示由状态（X,t）出发，在A上先加工零件i ， 然后再对以后的零件采取最优加工顺序后，将X中所有零件加工 完所需的时间。注意，这时t表示从零件i-1在A上加工完的时刻算 起直到在B上把它加工完所需的时间
令人(X,)表示由状态(Xt)出发，在A上相继加工零 件，，然后再对以后的零件采取最优加工顺序后，将X中所有 零件加工完所需的时间。 于是，不难得到 xD8/4 当ta时 当t长a时 其中X表示集合X去掉后剩下的零件集合。 记Z-(t)=max(ta,0}+b,它表示从X/i出发，从零件i在A上 加工完的时刻算起直到在B上把它加工完所需的时间。从而 f(X.ti)=a+f (X/i,Z (t)) 同理f(Xt,ij)a+a+f(XWij},Z,(t)) 其中Z(t)表示从X出发，在A上相继加工零件，从A将加工 完的时刻算起直到在B上把加工完所需的时间。从而 Z (t)=max (Z (t)-aj,0)+b=max {max[t-a.0]+b,a.0)+b -max (max t-a +bi a b a).0)+b -max t-a;a+b;+bibitb aj.b
令f（X,t,i,j）表示由状态（X,t）出发，在A上相继加工零 件i,j，然后再对以后的零件采取最优加工顺序后，将X中所有 零件加工完所需的时间。 于是，不难得到 ai+ f（X/i,t-ai+bi），当t≥ai时 f（X,t,i）= ai+ f（X/i, bi）， 当t≤ai时 其中X/i表示集合X去掉i后剩下的零件集合。 记 Zi（t）=max｛ t-ai ,0｝+bi，它表示从X/i出发,从零件i在A上 加工完的时刻算起直到在B上把它加工完所需的时间。从而 f（X,t,i）=ai+ f（X/i, Zi（t）） 同理 f（X,t,i,j）=ai+ aj + f（X/｛i,j｝, Zij（t）） 其中Zij（t）表示从X出发, 在A上相继加工零件i,j，从A将j加工 完的时刻算起直到在B上把j加工完所需的时间。从而 Zij（t）=max｛Zi（t）-aj,0｝+ bj=max｛max[t-ai ,0]+bi-aj ,0}+bj =max｛max（ t-ai+bi-aj ,bi-aj ),0}+bj =max｛ t-ai-aj+bi+bj ,bi+bj-aj ,bj}
由 f(X.tij)=a+a+f (X/(ij)Z (t) 及 Z (t)=max t-a a+b+bi.btb a b 将对调，即先加正，后加工i,则有 f (Xtj.i)-a+a+f(X/(ij)Z (t)) Z(t)=max t-aj-a+b,tbb+b aj.b) 由手fX)是的单调上升函数，敌当2，t)Zt)时 fX (ij)Z())sf(x/TijZ(D) 从而f(X,t,)≤f(X,) 这就是说，不管t值为何，当Z(t)≤工(t)时，零件放在零 件之前加还可以使总的加工时间短些。而由Z(t)和Z(t) 的表达式可知，这只须下面的不等式成立即可。即 max {b+b-ab max (b+b-ab 将上面不等式两边同时减去b,与b得 max {-a-b)<max {-a,-b) 即 mina,b}≥min{a,b} 这个条件就是零件应该排在零件之前的条件
由 f（X,t,i,j）=ai+ aj + f（X/｛i,j｝, Zij（t）） 及 Zij（t）=max｛ t-ai-aj+bi+bj ,bi+bj-aj ,bj} 将i,j对调，即先加工j,后加工i，则有 f（X,t,j,i）=ai+ aj + f（X/｛i,j｝, Zji（t）） Zji（t）=max｛ t-ai-aj+bi+bj ,bi+bj-ai ,bi} 由于f（X,t）是t的单调上升函数，故当Zij（t）≤Zji（t）时 f（X/｛i,j｝, Zij（t）） ≤ f（X/｛i,j｝, Zji（t）） 从而 f（X,t,i,j）≤ f（X,t,j,i） 这就是说，不管t值为何，当Zij（t）≤Zji（t）时，零件i放在零 件j之前加工可以使总的加工时间短些。而由Zij（t）和Zji（t） 的表达式可知，这只须下面的不等式成立即可。即 max｛bi+bj-aj ,bj}≤ max｛bi+bj-ai ,bi} 将上面不等式两边同时减去bi与bj得 max｛-aj ,-bi}≤max｛-ai ,-bj} 即 min｛aj ,bi}≥min｛ai ,bj} 这个条件就是零件i应该排在零件j之前的条件
由条件min(a,b2min(a,b}可知：当a小于a,b,b时， 先安排加工零件：当b小于aa,b时后安排加正零件，可以 使总的加工时间短些。由此得到最优排序操作方法如下： )写出工时矩阵a1a2,an bi b2...bn 找出工时矩阵中的最小元素，若它在上行，则将相应的零 件排在最前面位置；若它在下行，则将相应的零件排在最后面 位置。 2)将排定位置的零件所对应的列从矩阵中划掉，然后对余 下的零件重复()的操作，但那时最前（后位置是在已排定位 置之后（前。如此作下去，直到把所有零件都排完为止
由条件 min｛aj ,bi}≥min｛ai ,bj}可知：当ai小于aj，bi，bj时， 先安排加工零件i；当bj小于ai，aj，bi时后安排加工零件j,可以 使总的加工时间短些。由此得到最优排序操作方法如下： ⑴写出工时矩阵 a1 a2 … an b1 b2 … bn 找出工时矩阵中的最小元素，若它在上行，则将相应的零 件排在最前面位置；若它在下行，则将相应的零件排在最后面 位置。 ⑵将排定位置的零件所对应的列从矩阵中划掉，然后对余 下的零件重复⑴的操作，但那时最前（后）位置是在已排定位 置之后（前）。如此作下去，直到把所有零件都排完为止
例8设有5个零件在机床A、B上加工，加工顺序是先A后B, 每个零件所需加工时间如下表所示。试确定加工顺序，使机床 连续加工完所有零件的加工总时间最少，并求出总时间。 零件号 23 45 机床A 时 机床B 62732 34757 由此得最优加工顺序为：1一35一4→2 按加工顺序及所需时间绘示意图（称为甘特图）如下： 34 7 5 7 7 B 6图 40332 由甘特图可知，最少总加玉时间为28小时
例8 设有5个零件在机床A、B上加工，加工顺序是先A后B， 每个零件所需加工时间如下表所示。试确定加工顺序，使机床 连续加工完所有零件的加工总时间最少，并求出总时间。 零件号 1 2 3 4 5 加 工 时 间 机床A 3 7 4 5 7 机床B 6 2 7 3 4 解：工时矩阵为 3 7 4 5 7 6 2 7 3 4 7 2 3 6 5 3 4 7 7 4 由此得最优加工顺序为：1→3→5→4→2 按加工顺序及所需时间绘示意图（称为甘特图）如下： A B 3 4 7 5 7 6 7 4 3 3 2 由甘特图可知，最少总加工时间为28小时