動態(tài)規(guī)劃的應用排序問題

1、動態(tài)規(guī)劃的應用 排 序 問 題主要內容一、排序問題的介紹一、排序問題的介紹二、動態(tài)規(guī)劃方法的簡單介紹二、動態(tài)規(guī)劃方法的簡單介紹三、排序問題的求解三、排序問題的求解 排序（scheduling）問題產生的背景主要是機器制造，后來被廣泛應用于計算機系統(tǒng)、運輸調度、生產管理等領域。 排序問題是指在一定的約束條件下對工件和機器按時間進行分配和安排次序，使某一個或某一些目標達到最優(yōu)。 工件是被加工的對象，是要完成的任務；機器是提供加工的對象，是完成任務所需要的資源。 一、排序問題的介紹多臺機器的排序問題單臺機器的排序問題單件作業(yè)（Job-shop）排序問題： 工件的加工路線不同流水作業(yè)（Flow-sho

2、p）排序問題： 所有工件的加工路線完全相同排序問題的分類：下面主要介紹三種排序問題：下面主要介紹三種排序問題： 1 1、一臺機器、一臺機器、n n個工件的排序問題個工件的排序問題 2 2、兩臺機器、兩臺機器、n n個工件的排序問題個工件的排序問題 3 3、 n nm mP /Fmax P /Fmax 排序問題排序問題 如果我們用如果我們用PiPi表示安排在第表示安排在第i i位加工的零件位加工的零件所需的時間，用所需的時間，用TjTj表示安排在第表示安排在第j j位加工的零位加工的零件在車間里總的停留時間，則有件在車間里總的停留時間，則有 TjTj = = P1P1 + + P2P2 + +

3、Pj-1Pj-1 + + PjPj = = 不同的加工順序得到不同的各零件的平均不同的加工順序得到不同的各零件的平均停留時間，如何得到一個使得各零件的平均停停留時間，如何得到一個使得各零件的平均停留時間最少的排序呢？留時間最少的排序呢？ 對于某種加工順序，我們知道安排在第對于某種加工順序，我們知道安排在第j j位加工的零件在車間里總的停留時間為位加工的零件在車間里總的停留時間為TjTj ， Tj Tj = = jiiP11 1、一臺機器、一臺機器、n n個工件的排序問題個工件的排序問題jiiP1 例例 某車間只有一臺高精度的磨床，常常出現(xiàn)很多零某車間只有一臺高精度的磨床，常常出現(xiàn)很多零件同時要

4、求這臺磨床加工的情況，現(xiàn)有六個零件同件同時要求這臺磨床加工的情況，現(xiàn)有六個零件同時要求加工，這六個零件加工所需時間如下表所示。時要求加工，這六個零件加工所需時間如下表所示。 應該按照什么樣的加工順序來加工這六個零件，才應該按照什么樣的加工順序來加工這六個零件，才能使得這六個零件在車間里停留的平均時間為最少？能使得這六個零件在車間里停留的平均時間為最少？零件零件加工時間加工時間（小時）（小時）零件零件加工時間加工時間（小時）（小時）1 12 23 31.81.82.02.00.50.54 45 56 60.90.91.31.31.51.5 623456654321pppppP 可知這六個零件的停

5、留時間為：可知這六個零件的停留時間為： T T1 1 + + T T2 2 + + T T3 3 + + T T4 4 + + T T5 5 + + T T6 6 P P1 1 + ( + ( P P1 1 + + P P2 2 ) + ) + ( (P P1 1 + + P P2 2 + + P P3 3 ) + ( ) + (P P1 1 + + P P2 2 + + P P3 3 + + P P4 4 ) +( ) +(P P1 1 + + P P2 2 + + P P3 3 + + P P4 4 + + P P5 5) + () + (P P1 1 + + P P2 2 + + P P

6、3 3 + + P P4 4 + + P P5 5 + + P P6 6 ) ) 6 6 P P1 1 + 5 + 5 P P2 2 + 4 + 4P P3 3 + 3 + 3P P4 4 + 2 + 2P P5 5 + + P P6 6. . 那么各個零件平均停留時間為那么各個零件平均停留時間為 從上式可知，對于一臺機器從上式可知，對于一臺機器n n個零件的排序問題，個零件的排序問題，只要系數(shù)越大，配上加工時間越少的，即按照加工時只要系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后

7、面，可使各個零件的平加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。均停留時間為最少。2 2、兩臺機器、兩臺機器、n n個工件的排序問題個工件的排序問題 即即n n 種零件經過種零件經過2 2 種設備進行加工，種設備進行加工，如何安排？如何安排？ 設有n個工件需要在機床A、B上加工，每個工件都必須先經過A而后B兩道加工工序。以ai、bi分別表示工件i(1in)在A、B上的加工時間。問應如何在兩機床上安排各工件的加工順序，使在機床A上加工第一個工件開始到在機床B上加工完最后一個工件為止，所用的加工總時間最少？分析： 加工工件在機床A上有加工順序問題，在機床B上也有加工順序問題?？?/p>

8、以證明：最優(yōu)加工順序在兩臺機床上可同時實現(xiàn)。因此，最優(yōu)排序方案可以只在機床A、B上加工順序相同的排序中尋找。即使如此，所有可能的方案仍有n!個，這是一個不小的數(shù)，用窮舉法是不現(xiàn)實的。動態(tài)規(guī)劃思想：動態(tài)規(guī)劃思想： 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。二、動態(tài)規(guī)劃方法的簡單介紹二、動態(tài)規(guī)劃方法的簡單介紹 能用動態(tài)規(guī)劃方法求解的多階段決策能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，過程是一類特殊的多階段決策過程，即具有即具有無后效性無后效性的多階段決策過程。的多階段決策過程。

9、狀態(tài)具有無后效性的多階段決策過程狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉移方程如下：的狀態(tài)轉移方程如下：),(),(),(122231112kkkkusTsusTsusTs 動態(tài)規(guī)劃中能動態(tài)規(guī)劃中能處理的狀態(tài)轉移處理的狀態(tài)轉移方程的形式方程的形式。 動態(tài)規(guī)劃方法的關鍵在于正確地動態(tài)規(guī)劃方法的關鍵在于正確地寫出基本的遞推關系式和恰當?shù)倪吔鐚懗龌镜倪f推關系式和恰當?shù)倪吔鐥l件。要做到這一點，就必須將問題條件。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰的過程分成幾個相互聯(lián)系的階段，恰當?shù)漠數(shù)倪x取狀態(tài)變量和決策變量及定義選取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)最優(yōu)值函數(shù)，從而把一個大問題

10、轉化，從而把一個大問題轉化成一組同類型的子問題，然后逐個求成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結果，用了它前面的子問題的最優(yōu)化結果，依次進行，依次進行，最后一個子問題所得的最最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。優(yōu)解，就是整個問題的最優(yōu)解。動態(tài)規(guī)劃方法的步驟：(1) (1) 將所研究問題的過程劃分為將所研究問題的過程劃分為n n個恰當?shù)膫€恰當?shù)碾A段，階段，k k 1,2,n1,2,n；(2) (2) 正確地選擇狀態(tài)變量正確地選擇狀態(tài)變

11、量SkSk，并確定初始狀態(tài)并確定初始狀態(tài)S1S1的值；的值；(3) (3) 確定決策變量確定決策變量ukuk以及各階段的允許決策集以及各階段的允許決策集Dk(Sk)Dk(Sk)；(4) (4) 給出狀態(tài)轉移方程；給出狀態(tài)轉移方程；(5) (5) 給出滿足要求的過程指標函數(shù)給出滿足要求的過程指標函數(shù)Vk,nVk,n及相應的最優(yōu)及相應的最優(yōu) 值函數(shù)；值函數(shù)；(6) (6) 寫出遞推方程和邊界條件，建立基本方程；寫出遞推方程和邊界條件，建立基本方程；(7) (7) 按照基本方程遞推求解。按照基本方程遞推求解。 以上步驟是動態(tài)規(guī)劃法處理問題的基本步驟，其中以上步驟是動態(tài)規(guī)劃法處理問題的基本步驟，其中的

12、前六步是建立動態(tài)規(guī)劃模型的步驟。的前六步是建立動態(tài)規(guī)劃模型的步驟。問題： 如何用動態(tài)規(guī)劃方法來研究同順序兩臺機床加工N個工件的排序問題？ 排序問題提出一些假設條件：一個工件不能同時在幾臺機器上加工工件在加工過程中采取平行移動方式不允許中斷每道工序只在一臺機器上完成工件數(shù)、機器數(shù)和加工時間已知加工時間與加工順序無關每臺機器同時只能加工一個工件三、排序問題的求解三、排序問題的求解動態(tài)規(guī)劃求解 最優(yōu)排序方案：盡量減少在B上等待加工的時間，使總加工時間最短。 階段：機床A上更換工件的時刻k=1， 2，n。 狀態(tài)變量：（X,t） X: 在機床A上等待加工的的工件集合。 x：不屬于X的在A上最后加工完的工

13、件。 t: 在A上加工完x的時刻算起到B上加工完x所需的時間。 指標最優(yōu)值函數(shù)： f（X,t）:由狀態(tài)（X,t）出發(fā)，對未加工的工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時間。 f（X,t,i）:由狀態(tài)（X,t）出發(fā)，在A上加工工件i,然后再對未加工工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時間。 f（X,t,i,j）：由狀態(tài)（X,t）出發(fā)，在A上加工工件i、j,然后再對未加工工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時間。 狀態(tài)轉移： (X,t) (X/i,zi(t)當tai時當tai時ai工件工件i iAB工件工件i-1i-1工件工件i-1i-1bibittt-ai+bi

14、時當時當iitt),/(),/(),(aabiXfabatiXfaitXfiiiii)(,/),()0,max()(tziXfaitXfbattziiiiiX/i表示在集合X中去掉工件i后剩下的工件集合Zi(t)表示從狀態(tài)(X,t)出發(fā)，從在A上加工完i工件時刻算起到在B上加工完i工件所用的時間。（X,t） （X/i,j,zij(t) )(,/), , ,(tzjiXfaajitXfijji),max(0 ,)(max)(jjjijijijjiijbabbbbaatbatztz),max()(iijijijijibabbbbaattz),(tXf隨t單調增加，所以當 Zij（t） Zji（t）

15、),(),(ijtXfjitXf，成立),min(),min(),max(),max(biajbjaibiaibjbibjajbjbi工件i放在工件j前面的條件：即當ai小于bi、aj、bj或bj小于ai、aj、bi時，先安排工件i加工。根據(jù)上述條件，構造最優(yōu)排序規(guī)則： a1 a2 an 建立工時矩陣 M= b1 b2 bn 在工時矩陣M中找出最小元素（若不止一個可任選其一），若它在上行，則相應的工件排在最前位置；若它在下行，則相應的工件排在最后位置。 將排定位置的工件所對應的列從M中劃去，然后對余下的工件再進行排序。如此進行下去，直到把所有工件都排完為止。例題：4 49 95 52 23 3

16、B B5 53 37 78 86 6A A 零件零件2j1j3j4j5j設備設備工件的加工工時矩陣為： M= 根據(jù)最優(yōu)排序規(guī)則,求解過程可簡單表示如下： 將工件2排第5位 2將工件4排第1位 4 2將工件1排第4位 4 1 2將工件5排第3位 4 5 1 2將工件3排第2位 4 3 5 2 1 最優(yōu)加工順序為： j4，j3，j5，j1，j24593572836加工周期 T = 3+7+5+6+8+2 = 31 加工順序圖如下： j4 j3 j5 j1 j2ABTABT3756895432+2+2-53、nmP /Fmax 排序問題 這里所討論的是nmP /Fmax，問題，其中n為工件數(shù)， m為

17、機器數(shù)，P表示流水線作業(yè)排列排序問題，F(xiàn)max為目標函數(shù)。目標函數(shù)是使最長流程時間最短，最長流程時間又稱作加工周期，它是從第一個工件在第一臺機器開始加工時算起，到最后一個工件在最后一臺機器上完成加工時為止所經過的時間。由于假設所有工件的到達時間都為零(ri=0， i= 1，2，n)，所以Fmax等于排在末位加工的工件在車間的停留時間，也等于一批工件的最大完工時間Cmax。設n個工件的加工順序為S(S1，S2，S3，Sn)，其中Si為第i位加工的工件的代號。以 表示工件Si在機器 M k上的完工時間, 表示工件Si在 Mk上的加工時間，k= 1，2，m； i=1，2，n，則可按以下公式計算： 以 表示工件Si在機器 上的完工時間， 表示工件Si在機器 上的加工時間，k=1,2,m;i=1,2,n。則有： k=2,3,m;i=1,2,n iskCkMkiSpkM1111iisisspCCkiisisisskkkpCCC,max1)1(nsmCFmax例 有一個64pF max問題，其加工時間如表96所示。當按順序S=(6，1，5，2，4，3)加工時，求 Fmax 。