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

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

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

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

5、留時(shí)間為：可知這六個(gè)零件的停留時(shí)間為： 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. . 那么各個(gè)零件平均停留時(shí)間為那么各個(gè)零件平均停留時(shí)間為 從上式可知，對(duì)于一臺(tái)機(jī)器從上式可知，對(duì)于一臺(tái)機(jī)器n n個(gè)零件的排序問題，個(gè)零件的排序問題，只要系數(shù)越大，配上加工時(shí)間越少的，即按照加工時(shí)只要系數(shù)越大，配上加工時(shí)間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，間排出加工順序，加工時(shí)間越少的零件排在越前面，加工時(shí)間越多的零件排在越后

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

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

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

10、轉(zhuǎn)化，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求成一組同類型的子問題，然后逐個(gè)求解。即從邊界條件開始，逐段遞推尋解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，依次進(jìn)行，最后一個(gè)子問題所得的最最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。優(yōu)解，就是整個(gè)問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法的步驟：(1) (1) 將所研究問題的過程劃分為將所研究問題的過程劃分為n n個(gè)恰當(dāng)?shù)膫€(gè)恰當(dāng)?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)轉(zhuǎn)移方程；給出狀態(tài)轉(zhuǎn)移方程；(5) (5) 給出滿足要求的過程指標(biāo)函數(shù)給出滿足要求的過程指標(biāo)函數(shù)Vk,nVk,n及相應(yīng)的最優(yōu)及相應(yīng)的最優(yōu) 值函數(shù)；值函數(shù)；(6) (6) 寫出遞推方程和邊界條件，建立基本方程；寫出遞推方程和邊界條件，建立基本方程；(7) (7) 按照基本方程遞推求解。按照基本方程遞推求解。 以上步驟是動(dòng)態(tài)規(guī)劃法處理問題的基本步驟，其中以上步驟是動(dòng)態(tài)規(guī)劃法處理問題的基本步驟，其中的

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

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

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

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

16、B B5 53 37 78 86 6A A 零件零件2j1j3j4j5j設(shè)備設(shè)備工件的加工工時(shí)矩陣為： M= 根據(jù)最優(yōu)排序規(guī)則,求解過程可簡(jiǎn)單表示如下： 將工件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)加工順序?yàn)椋?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、機(jī)器數(shù)，P表示流水線作業(yè)排列排序問題，F(xiàn)max為目標(biāo)函數(shù)。目標(biāo)函數(shù)是使最長(zhǎng)流程時(shí)間最短，最長(zhǎng)流程時(shí)間又稱作加工周期，它是從第一個(gè)工件在第一臺(tái)機(jī)器開始加工時(shí)算起，到最后一個(gè)工件在最后一臺(tái)機(jī)器上完成加工時(shí)為止所經(jīng)過的時(shí)間。由于假設(shè)所有工件的到達(dá)時(shí)間都為零(ri=0， i= 1，2，n)，所以Fmax等于排在末位加工的工件在車間的停留時(shí)間，也等于一批工件的最大完工時(shí)間Cmax。設(shè)n個(gè)工件的加工順序?yàn)镾(S1，S2，S3，Sn)，其中Si為第i位加工的工件的代號(hào)。以 表示工件Si在機(jī)器 M k上的完工時(shí)間, 表示工件Si在 Mk上的加工時(shí)間，k= 1，2，m； i=1，2，n，則可按以下公式計(jì)算： 以 表示工件Si在機(jī)器 上的完工時(shí)間， 表示工件Si在機(jī)器 上的加工時(shí)間，k=1,2,m;i=1,2,n。則有： k=2,3,m;i=1,2,n iskCkMkiSpkM1111iisisspCCkiisisisskkkpCCC,max1)1(nsmCFmax例 有一個(gè)64pF max問題，其加工時(shí)間如表96所示。當(dāng)按順序S=(6，1，5，2，4，3)加工時(shí)，求 Fmax 。