運(yùn)營管理第11章制造業(yè)作業(yè)計(jì)劃與控制

1、流水作業(yè)排序問題流水作業(yè)排序問題單件作業(yè)排序問題單件作業(yè)排序問題 重點(diǎn)重點(diǎn)內(nèi)容內(nèi)容排序問題的基本概念排序問題的基本概念流水作業(yè)排序問題流水作業(yè)排序問題單件作業(yè)排序問題單件作業(yè)排序問題生產(chǎn)作業(yè)控制生產(chǎn)作業(yè)控制 第第11章章 制造業(yè)作業(yè)計(jì)劃與控制制造業(yè)作業(yè)計(jì)劃與控制 生產(chǎn)作業(yè)計(jì)劃的主要任務(wù)是將主生產(chǎn)計(jì)劃或生產(chǎn)作業(yè)計(jì)劃的主要任務(wù)是將主生產(chǎn)計(jì)劃或MRP中的零中的零部件投入出產(chǎn)計(jì)劃細(xì)化，是部件投入出產(chǎn)計(jì)劃細(xì)化，是MRP的具體執(zhí)行計(jì)劃，具體、的具體執(zhí)行計(jì)劃，具體、詳細(xì)地規(guī)定了各車間、工段、班組以至每個(gè)工作地在較詳細(xì)地規(guī)定了各車間、工段、班組以至每個(gè)工作地在較短的時(shí)間內(nèi)（月、旬、周、日、輪班、小時(shí)）的生產(chǎn)運(yùn)

2、短的時(shí)間內(nèi)（月、旬、周、日、輪班、小時(shí)）的生產(chǎn)運(yùn)作任務(wù)。作任務(wù)。生產(chǎn)作業(yè)計(jì)劃的內(nèi)容生產(chǎn)作業(yè)計(jì)劃的內(nèi)容作業(yè)計(jì)劃與控制的關(guān)系作業(yè)計(jì)劃與控制的關(guān)系l作業(yè)計(jì)劃：作業(yè)計(jì)劃： 給生產(chǎn)活動(dòng)制定詳細(xì)時(shí)間表給生產(chǎn)活動(dòng)制定詳細(xì)時(shí)間表l生產(chǎn)控制：生產(chǎn)控制： 以生產(chǎn)計(jì)劃和作業(yè)計(jì)劃為依據(jù)，檢查、落實(shí)計(jì)劃執(zhí)行情以生產(chǎn)計(jì)劃和作業(yè)計(jì)劃為依據(jù)，檢查、落實(shí)計(jì)劃執(zhí)行情況，發(fā)現(xiàn)偏差即采取糾正措施，保證實(shí)現(xiàn)各項(xiàng)各項(xiàng)計(jì)劃目況，發(fā)現(xiàn)偏差即采取糾正措施，保證實(shí)現(xiàn)各項(xiàng)各項(xiàng)計(jì)劃目標(biāo)。標(biāo)。第一節(jié)第一節(jié) 排序問題的基本概念排序問題的基本概念 一、名詞術(shù)語一、名詞術(shù)語 生產(chǎn)管理生產(chǎn)管理 “（編制）作業(yè)計(jì)劃（編制）作業(yè)計(jì)劃”（Scheduling）“排

3、序排序”（Sequencing）“派工派工”（Dispatching）“控制控制”（Controlling）“趕工趕工”（Expediting） 排序排序 工件在機(jī)器上的加工順序工件在機(jī)器上的加工順序 （編制）作業(yè)計(jì)劃（編制）作業(yè)計(jì)劃 工件的加工順序工件的加工順序 加工工件的開始時(shí)間加工工件的開始時(shí)間加工工件的完成時(shí)間加工工件的完成時(shí)間 作業(yè)計(jì)劃的主要問題是確定各臺(tái)機(jī)器上工件的加工順序作業(yè)計(jì)劃的主要問題是確定各臺(tái)機(jī)器上工件的加工順序 通常情況下都是按最早可能開（完）工時(shí)間來編排作業(yè)通常情況下都是按最早可能開（完）工時(shí)間來編排作業(yè)計(jì)劃的計(jì)劃的 當(dāng)工件的加工順序確定之后，作業(yè)計(jì)劃也就確定了當(dāng)工件的

4、加工順序確定之后，作業(yè)計(jì)劃也就確定了 派工派工 趕工趕工 屬于屬于“調(diào)度調(diào)度”范圍范圍 “編制作業(yè)計(jì)劃編制作業(yè)計(jì)劃”加工制造發(fā)生之前的活動(dòng)加工制造發(fā)生之前的活動(dòng) “調(diào)度調(diào)度”是在加工制造發(fā)生之后的活動(dòng)，是發(fā)現(xiàn)實(shí)生產(chǎn)是在加工制造發(fā)生之后的活動(dòng)，是發(fā)現(xiàn)實(shí)生產(chǎn)進(jìn)度已經(jīng)偏離預(yù)定計(jì)劃而采取的調(diào)配資源的行動(dòng)進(jìn)度已經(jīng)偏離預(yù)定計(jì)劃而采取的調(diào)配資源的行動(dòng)調(diào)度的依據(jù)是作業(yè)計(jì)劃調(diào)度的依據(jù)是作業(yè)計(jì)劃 描述排序問題的術(shù)語描述排序問題的術(shù)語 “機(jī)器機(jī)器” “工件工件” “工序工序” “加工時(shí)間加工時(shí)間” n個(gè)工件經(jīng)過個(gè)工件經(jīng)過m臺(tái)機(jī)器加工臺(tái)機(jī)器加工 “加工路線加工路線” 工件加工的工藝過程決定工件加工的工藝過程決定 一般

5、用一般用M1，M2，來表示來表示“加工順序加工順序” 每臺(tái)機(jī)器加工每臺(tái)機(jī)器加工n個(gè)工件的先后順序個(gè)工件的先后順序 排序問題的復(fù)雜性排序問題的復(fù)雜性確定出最佳的作業(yè)順序看似容易，只要列出所有的順序，確定出最佳的作業(yè)順序看似容易，只要列出所有的順序，然后再從中挑出最好的就可以了，但要實(shí)現(xiàn)這種想法幾然后再從中挑出最好的就可以了，但要實(shí)現(xiàn)這種想法幾乎是不可能的。乎是不可能的。例如，考慮例如，考慮32項(xiàng)任務(wù)（工件），有項(xiàng)任務(wù)（工件），有32！ 2.6 1035 種方案種方案,假定計(jì)算機(jī)每秒鐘可以檢查假定計(jì)算機(jī)每秒鐘可以檢查1 billion個(gè)順序個(gè)順序, 全部檢驗(yàn)完全部檢驗(yàn)完畢需要畢需要8.4 1015

6、 個(gè)世紀(jì)。個(gè)世紀(jì)。如果只有如果只有16個(gè)工件個(gè)工件, 同樣按每秒鐘可以檢查同樣按每秒鐘可以檢查1 billion個(gè)順個(gè)順序計(jì)算序計(jì)算, 也需要也需要2/3年。年。以上問題還沒有考慮其他的約束條件以上問題還沒有考慮其他的約束條件, 如機(jī)器、人力資如機(jī)器、人力資源、廠房場地等，如果加上這些約束條件，所需要的時(shí)源、廠房場地等，如果加上這些約束條件，所需要的時(shí)間就無法想象了。間就無法想象了。所以，很有必要去尋找一些有效算法，解決管理中的實(shí)所以，很有必要去尋找一些有效算法，解決管理中的實(shí)際問題。際問題。二、假設(shè)條件與符號(hào)說明二、假設(shè)條件與符號(hào)說明 假設(shè)條件假設(shè)條件 l. 一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器

7、上加工一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工 2. 工件在加工過程中采取平行移動(dòng)方式工件在加工過程中采取平行移動(dòng)方式3.不允許中斷不允許中斷4. 每道工序只在一臺(tái)機(jī)器上完成每道工序只在一臺(tái)機(jī)器上完成 5.工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無關(guān)工順序無關(guān) 6.每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件 符號(hào)符號(hào) Ji工件工件i ，i= 1，2，n Mj機(jī)器機(jī)器j，j=1，2，m PijJi在在Mj上的加工時(shí)間，上的加工時(shí)間，Ji的總加工時(shí)間為的總加工時(shí)間為Pi=pij riJi的到達(dá)時(shí)間，指的到達(dá)時(shí)間，指Ji從外部進(jìn)入車間，可

8、以開從外部進(jìn)入車間，可以開始加工的最早時(shí)間始加工的最早時(shí)間 diJi的完工期限的完工期限 CiJi的完工時(shí)間，的完工時(shí)間，Ciri +(wij+pij)=ri+Wi+Pi Cmax最長完工時(shí)間，最長完工時(shí)間，Cmax=maxCi 符號(hào)符號(hào) FiJi的流程時(shí)間，即工件在車間的實(shí)際停留時(shí)間，的流程時(shí)間，即工件在車間的實(shí)際停留時(shí)間，F(xiàn)iCi-ri=Wi+Pi Fmax最長流程時(shí)間，最長流程時(shí)間，F(xiàn)max=maxFi Li工件的延遲時(shí)間工件的延遲時(shí)間 WijJi在在Mj上加工之前的等待時(shí)間上加工之前的等待時(shí)間 WiJi在加工過程中總的等待時(shí)間在加工過程中總的等待時(shí)間 aiJi的允許停留時(shí)間的允許停留時(shí)

9、間 符號(hào)符號(hào) Li=Ci-di=ri+Pi+Wi-di=(Pi+Wi)-(di-ri)=Fi-ai當(dāng)當(dāng)Li0（正延遲），說明（正延遲），說明Ji的實(shí)際完工時(shí)間超的實(shí)際完工時(shí)間超過了完工期限過了完工期限當(dāng)當(dāng)Li0（負(fù)延遲），說明（負(fù)延遲），說明Ji提前完工提前完工當(dāng)當(dāng)Li=0（零延遲），（零延遲），Ji按期按期完工完工 Lmax最長延遲時(shí)間，最長延遲時(shí)間，Lmax=maxLi 三、排序問題的分類和表示法三、排序問題的分類和表示法 分類方法分類方法 機(jī)器機(jī)器 工件工件 目標(biāo)函數(shù)目標(biāo)函數(shù) 機(jī)器機(jī)器 單臺(tái)機(jī)器的排序問題單臺(tái)機(jī)器的排序問題 多臺(tái)機(jī)器的排序問題多臺(tái)機(jī)器的排序問題 工件加工路線工件加工路線

10、單件作業(yè)（單件作業(yè)（Job-Shop）排序問題）排序問題 流水作業(yè)（流水作業(yè)（Flow-shop）排序問）排序問題題 單件車間排序問題的基本特征：單件車間排序問題的基本特征：每個(gè)工件都有其獨(dú)特的加每個(gè)工件都有其獨(dú)特的加工路線，工件沒有一定的流向。工路線，工件沒有一定的流向。流水車間排序問題的基本特征：流水車間排序問題的基本特征：每個(gè)工件的加工路線都一樣。如車每個(gè)工件的加工路線都一樣。如車銑銑磨。這里指的是磨。這里指的是工件的加工流向一致，并不要求每個(gè)工件必須在每臺(tái)機(jī)器工件的加工流向一致，并不要求每個(gè)工件必須在每臺(tái)機(jī)器上加工。如有的工件為車上加工。如有的工件為車磨，有的為銑磨，有的為銑磨。磨。不

11、僅加工路線一致，而且所有工件在各臺(tái)機(jī)器上的加工順不僅加工路線一致，而且所有工件在各臺(tái)機(jī)器上的加工順序也一樣，這種排序稱為序也一樣，這種排序稱為排列排序（同順序排序）排列排序（同順序排序）。如工。如工件排序?yàn)椋杭判驗(yàn)椋篔1J3J2，則表示所有機(jī)器都是先加工，則表示所有機(jī)器都是先加工J1，然，然后加工后加工J3，最后加工，最后加工J2。靜態(tài)的排序問題靜態(tài)的排序問題動(dòng)態(tài)的排序問題動(dòng)態(tài)的排序問題 單目標(biāo)排序問題單目標(biāo)排序問題多目標(biāo)排序問題多目標(biāo)排序問題 確定型排序問題確定型排序問題隨機(jī)型排序問題隨機(jī)型排序問題 Conway表示方法表示方法4參數(shù)表示法參數(shù)表示法 nm A B n 工件數(shù)工件數(shù)m 機(jī)器

12、數(shù)機(jī)器數(shù)A 車間類型車間類型 F 代表流水作業(yè)排序問題代表流水作業(yè)排序問題P 表示流水作業(yè)排列排序問題表示流水作業(yè)排列排序問題G 表示一般單件作業(yè)排序問題表示一般單件作業(yè)排序問題m1 A 空白空白 B 目標(biāo)函數(shù)目標(biāo)函數(shù) 第二節(jié)第二節(jié) 流水作業(yè)排序問題流水作業(yè)排序問題 基本特征基本特征 工件的加工路線都一致工件的加工路線都一致 工件的流向一致，并不要求每個(gè)工件必須經(jīng)過工件的流向一致，并不要求每個(gè)工件必須經(jīng)過加工路線上每臺(tái)機(jī)器加工加工路線上每臺(tái)機(jī)器加工 對于流水作業(yè)排序問題，工件在不同機(jī)器上的加工順序?qū)τ诹魉鳂I(yè)排序問題，工件在不同機(jī)器上的加工順序不盡一致不盡一致 流水作業(yè)排列排序問題流水作業(yè)排列

13、排序問題 “同順序同順序”排序問題排序問題 所有工件在各臺(tái)機(jī)器上的加工順序都相同所有工件在各臺(tái)機(jī)器上的加工順序都相同 排列排序問題的最優(yōu)解不一定是相應(yīng)的流水作業(yè)排序問題排列排序問題的最優(yōu)解不一定是相應(yīng)的流水作業(yè)排序問題的最優(yōu)解，但一般是比較好的解的最優(yōu)解，但一般是比較好的解 對于僅有對于僅有2臺(tái)和臺(tái)和3臺(tái)臺(tái)機(jī)器的特殊情況，排列排序問題下的最優(yōu)機(jī)器的特殊情況，排列排序問題下的最優(yōu)解一定是相應(yīng)流水作業(yè)排序問題的最優(yōu)解解一定是相應(yīng)流水作業(yè)排序問題的最優(yōu)解 一、最長流程時(shí)間一、最長流程時(shí)間Fmax的計(jì)算的計(jì)算 nmPFmax 目標(biāo)函數(shù)目標(biāo)函數(shù)最長流程時(shí)間最最長流程時(shí)間最短短 最長流程時(shí)間最長流程時(shí)間加

14、工周期加工周期 從第一個(gè)工件在第一臺(tái)機(jī)器開始加工時(shí)算起，到從第一個(gè)工件在第一臺(tái)機(jī)器開始加工時(shí)算起，到最后一個(gè)工件在最后一臺(tái)機(jī)器上完成加工時(shí)為止最后一個(gè)工件在最后一臺(tái)機(jī)器上完成加工時(shí)為止所經(jīng)過的時(shí)間所經(jīng)過的時(shí)間 Fmax等于排在末位的工件在車間的停留時(shí)間，等等于排在末位的工件在車間的停留時(shí)間，等于一批工件的最長完工時(shí)間于一批工件的最長完工時(shí)間Cmax 設(shè)設(shè)n個(gè)工件的加工順序?yàn)閭€(gè)工件的加工順序?yàn)镾=（S1，S2，Sn） Si 排第排第i位加工的工件位加工的工件的代號(hào)的代號(hào) 表示工件表示工件Si在機(jī)器在機(jī)器Mk上的完工時(shí)間上的完工時(shí)間 iSkCkips表示工件表示工件Si在在Mk上的加工時(shí)間上的加工

15、時(shí)間 k=1，2，m i=1，2，n iSkC按以下公式計(jì)算按以下公式計(jì)算 1111ipsCCiSiSkikkkpsCCCkiSiSiS1,max1(11.1)k=1,2,m ;i=1,2,n 當(dāng)當(dāng)ri=0，i=1,2,n時(shí)時(shí) Fmax= nSmC例例11.1 有一個(gè)有一個(gè)64PFmax問題，其加工時(shí)間如表問題，其加工時(shí)間如表111所示。當(dāng)按順序所示。當(dāng)按順序S=(6,1,5,2,4,3)加工時(shí)，求加工時(shí)，求Fmax。i123456pi1423142pi 2456745pi 3587555pi 4424331表表11-l 加工時(shí)間矩陣加工時(shí)間矩陣 i615243pi12246410212113

16、316pi 257411415520727633pi 3512517522830535742pi 4113421325232338446表表112 順序順序S下的加工時(shí)間矩陣下的加工時(shí)間矩陣 二、二、n/2/F/ Fn/2/F/ Fmaxmax問題的最優(yōu)算法問題的最優(yōu)算法n項(xiàng)任務(wù)在兩臺(tái)機(jī)器的排序問題項(xiàng)任務(wù)在兩臺(tái)機(jī)器的排序問題Scheduling n Jobs on Two Machinesn個(gè)工件都必須經(jīng)過機(jī)器個(gè)工件都必須經(jīng)過機(jī)器1和機(jī)器和機(jī)器2的加工，即工藝路線的加工，即工藝路線是一致的。是一致的。機(jī)器機(jī)器1到達(dá)系統(tǒng)工到達(dá)系統(tǒng)工件的集合件的集合離開系統(tǒng)（離開系統(tǒng)（機(jī)器）機(jī)器）J1J2J3Jn

17、機(jī)器機(jī)器2兩臺(tái)機(jī)器排序問題的目標(biāo)兩臺(tái)機(jī)器排序問題的目標(biāo) 兩臺(tái)機(jī)器排序的目標(biāo)是使最大完成時(shí)間（總加工周期）兩臺(tái)機(jī)器排序的目標(biāo)是使最大完成時(shí)間（總加工周期）Fmax最短。最短。 Fmax的含義見如下的甘特圖的含義見如下的甘特圖(Gantt Chart)。 多臺(tái)機(jī)器排序的目標(biāo)一般也是使最大完成時(shí)間（總加多臺(tái)機(jī)器排序的目標(biāo)一般也是使最大完成時(shí)間（總加工周期）工周期） Fmax最短。最短。Fmax 時(shí)間時(shí)間 機(jī)器機(jī)器 A B在機(jī)器在機(jī)器A上的作業(yè)時(shí)間上的作業(yè)時(shí)間總加工周期總加工周期1954年年Johnson提出提出用用ai 表示表示Ji在在M1 上的加工時(shí)間，用上的加工時(shí)間，用bi 表示表示Ji在在M2

18、 上的加工時(shí)間。每個(gè)工件都按上的加工時(shí)間。每個(gè)工件都按M1 M2的路線加工。的路線加工。 Johnson指出，若指出，若min(ai, bj)=max Bior min Ci = max Bi 定義：定義：Ai = Ai+ Bi , Bi = Bi +Ci例例: 考慮以下問題考慮以下問題. 5個(gè)工件由個(gè)工件由3臺(tái)機(jī)器加工臺(tái)機(jī)器加工, 作業(yè)時(shí)間見下作業(yè)時(shí)間見下表表. 求求: 總加工周期最短的作業(yè)順序?？偧庸ぶ芷谧疃痰淖鳂I(yè)順序。 1 2 3 4 5機(jī)器機(jī)器A 44 913 821 627 532機(jī)器機(jī)器B 59 619 223 330 436機(jī)器機(jī)器C 817 1029 635 742 1153

19、解解: 檢查上表檢查上表, 發(fā)現(xiàn)發(fā)現(xiàn): min Ai = 4 max Bi = 6 min Ci = 6因此因此,滿足以上條件滿足以上條件, 建立兩臺(tái)機(jī)器的作業(yè)時(shí)間表建立兩臺(tái)機(jī)器的作業(yè)時(shí)間表: 1 2 3 4 5機(jī)器機(jī)器A 9 15 10 9 9機(jī)器機(jī)器B 13 16 8 10 15 1 4 5 2 3機(jī)器機(jī)器A 44 610 515 924 832機(jī)器機(jī)器B 59 313 419 630 234機(jī)器機(jī)器C 817 724 1135 1045 651應(yīng)用應(yīng)用Johnson法則，得出：法則，得出：總加工周期為：總加工周期為：三、三、n/m/P/Fmax問題的啟發(fā)式算法問題的啟發(fā)式算法 對于對于3

20、臺(tái)機(jī)器的流水車間排序問題，只有幾種特殊類型的臺(tái)機(jī)器的流水車間排序問題，只有幾種特殊類型的問題找到了有效算法問題找到了有效算法 對于一般的流水車間排列排序問題對于一般的流水車間排列排序問題 分支定界法分支定界法 啟發(fā)式算法啟發(fā)式算法 求一般求一般nmPFmax問題近優(yōu)解（問題近優(yōu)解（Near optimal solution）的啟發(fā)式算法的啟發(fā)式算法 （一）（一）Palmer法法 按斜度指標(biāo)排列工件的啟發(fā)式算法按斜度指標(biāo)排列工件的啟發(fā)式算法 工件斜度指標(biāo)工件斜度指標(biāo) mkikipmk121k=1,2,n m為機(jī)器數(shù)；為機(jī)器數(shù)；pik為工件為工件i在在Mk上的加工時(shí)間上的加工時(shí)間 按照各工件按照各

21、工件 不增的順序排列工件，可得出令人滿意不增的順序排列工件，可得出令人滿意的順序的順序 i(11.4)例例11.3 有一個(gè)有一個(gè)43FFmax問題，其加工時(shí)間如表問題，其加工時(shí)間如表115所示，用所示，用Palmer法求解法求解 i1234pi11263pi28429pi34582表表115 加工時(shí)間矩陣加工時(shí)間矩陣 解：對于本例，式（解：對于本例，式（114）變成）變成 mkikipmk121k=1,2,3 =- pk1+ pk3 i1234=- p11+ p13=-1+4=3 =- p21+ p23=-2+5=3 =- p31+ p33=-6+8=2 =- p41+ p43=-3+2=-1

22、 i按按 不增的順序排列工件，得到加工順序不增的順序排列工件，得到加工順序（l,2,3,4）和（和（2,l,3,4） 這兩個(gè)順序都是最優(yōu)順序這兩個(gè)順序都是最優(yōu)順序 Fmax28 （二）關(guān)鍵工件法（二）關(guān)鍵工件法 步驟步驟 （1）計(jì)算每個(gè)工件的總加工時(shí)間）計(jì)算每個(gè)工件的總加工時(shí)間Pi=pij，找出加工，找出加工時(shí)間最長的工件時(shí)間最長的工件C（j=m），將其作為關(guān)鍵工），將其作為關(guān)鍵工件。件。 （2）對于余下的工件，若）對于余下的工件，若pi1pim，則按，則按pi1不減的順不減的順序排成一個(gè)序列序排成一個(gè)序列Sa；若；若pi1pim，則按，則按pim不增不增的順序排列成一個(gè)序列的順序排列成一個(gè)序

23、列Sb。 （3）順序（）順序（Sa，C，Sb）即為所求順序。）即為所求順序。 i1234pi11263pi28429pi34582pi13111614表表11-6 用關(guān)鍵工件法求解用關(guān)鍵工件法求解 總加工時(shí)間最長的為總加工時(shí)間最長的為3號(hào)工件號(hào)工件 （三）（三）CDS法法 把把Johnson算法用于一般的算法用于一般的nmPFmax問題，得問題，得到（到（m-1）個(gè)加工順序，取其中優(yōu)者。）個(gè)加工順序，取其中優(yōu)者。 具體做法具體做法 lkikp1mlmkikp1按按和和合并組成新的合并組成新的“機(jī)器機(jī)器”l=1,2,m-1 合并合并(m-1)次，得到次，得到(m-1)個(gè)個(gè)n/2/F/Fmax問題

24、問題 用用Johnson算法求（算法求（m-1）次加工順序，取其中最好的結(jié)）次加工順序，取其中最好的結(jié)果果 11 , 1,2,.,1lmikikkk mlPPlm 和 用用 CDS 法法求求解解i 1 2 3 4Pi1 1 2 6 3L=1Pi3 4 5 8 2Pi1+pi2 9 6 8 12L=2Pi2+pi3 12 9 10 11 L1，按，按Johnson算法得到加工順序算法得到加工順序(1，2，3，4)，F(xiàn)max28 L2，按，按Johnson算法得到加工順序算法得到加工順序(2，3，1，4)， Fmax29 取順序取順序(1，2，3，4）為最優(yōu)順序。）為最優(yōu)順序。四、相同零件不同移動(dòng)

25、方式下加工周期四、相同零件不同移動(dòng)方式下加工周期的計(jì)算的計(jì)算排序問題針對的是不同的零件，如果排序問題針對的是不同的零件，如果n n個(gè)零件個(gè)零件相同，則沒有排序問題。相同，則沒有排序問題。零件在加工過程中采取的移動(dòng)方式不同，會(huì)導(dǎo)零件在加工過程中采取的移動(dòng)方式不同，會(huì)導(dǎo)致一批零件的加工周期不同。致一批零件的加工周期不同。零件在加工過程中可以采用三種典型的移動(dòng)方零件在加工過程中可以采用三種典型的移動(dòng)方式：式：順序移動(dòng)順序移動(dòng)平行移動(dòng)平行移動(dòng)平行順序移動(dòng)平行順序移動(dòng)第三節(jié)第三節(jié) 單件作業(yè)排序問題單件作業(yè)排序問題 每個(gè)工件都有其獨(dú)特的加工路線，工件沒有一定的流向每個(gè)工件都有其獨(dú)特的加工路線，工件沒有一定

26、的流向單件作業(yè)的排序問題是最一般的排序問題，也是最復(fù)雜的單件作業(yè)的排序問題是最一般的排序問題，也是最復(fù)雜的一種排序問題一種排序問題 R.w.Conway 作業(yè)計(jì)劃理論作業(yè)計(jì)劃理論（Theory of Scheduling）一、問題的描述一、問題的描述 對于一般單件作業(yè)排序問題對于一般單件作業(yè)排序問題 描述一道工序，要用描述一道工序，要用3個(gè)參數(shù)：個(gè)參數(shù)：i,j和和k i表示工件代號(hào)表示工件代號(hào)j表示工序號(hào)表示工序號(hào)k表示完成工件表示完成工件i的第的第j道工序的機(jī)器的代道工序的機(jī)器的代號(hào)號(hào) 用用（i,j,k）來表示工件）來表示工件i的第的第j道工序是在機(jī)器道工序是在機(jī)器k上進(jìn)行上進(jìn)行的這樣的這樣

27、一件事一件事 用加工描述矩陣描述所有工件的加工要求。用加工描述矩陣描述所有工件的加工要求。加工描述矩陣加工描述矩陣D 2 , 3 , 21 , 2 , 23 , 1 , 22 , 3 , 13 , 2 , 11 , 1 , 1D加工描述矩陣加工描述矩陣D的每一行描述一個(gè)工件的加工的每一行描述一個(gè)工件的加工 每一列的工序序號(hào)相同每一列的工序序號(hào)相同 行表示不同的工件；列表示不同的工序。行表示不同的工件；列表示不同的工序。單件作業(yè)排序問題單件作業(yè)排序問題(n/m/G/ Fmax)D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=4 6 35 7 4加工描述矩陣加工描述矩陣

28、D：每一行描述一個(gè)工件的加工，每一列的：每一行描述一個(gè)工件的加工，每一列的工序序號(hào)相同。工序序號(hào)相同。加工時(shí)間矩陣加工時(shí)間矩陣T：與：與D相對應(yīng)。相對應(yīng)。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3單件作業(yè)排序問題單件作業(yè)排序問題(n/m/G/ Fmax)加工順序矩陣加工順序矩陣S：每一行與機(jī)器相對應(yīng)，每一列與工件相對應(yīng)。：每一行與機(jī)器相對應(yīng)，每一列與工件相對應(yīng)。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,

29、2,3T=4 6 35 7 41,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3單件作業(yè)排序問題單件作業(yè)排序問題(n/m/G/ Fmax)用方塊圖表示：用方塊圖表示：二、一般二、一般n/m/G/Fmax問題的啟發(fā)式算法問題的啟發(fā)式算法 對于一般的對于一般的n/m/G/Fmax排序問題排序問題 分支定界法或整數(shù)規(guī)劃法分支定界法或整數(shù)規(guī)劃法 是無效算法是無效算法 啟發(fā)式算法是求解一般單件車間排序問題使用最多的方法啟發(fā)式算法是求解一般單件車間排序問題使用最多的方法 （一）兩種作業(yè)計(jì)劃的構(gòu)成（一）兩種作業(yè)計(jì)劃的構(gòu)成 半能動(dòng)作業(yè)計(jì)劃（半能動(dòng)作業(yè)計(jì)劃（Semi-active sche

30、dule） 各工序都按最早可能開（完）工時(shí)間安排的作業(yè)計(jì)劃各工序都按最早可能開（完）工時(shí)間安排的作業(yè)計(jì)劃 能動(dòng)作業(yè)計(jì)劃（能動(dòng)作業(yè)計(jì)劃（Active schedule） 任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序的半能動(dòng)作業(yè)劃工工序的半能動(dòng)作業(yè)劃 無延遲作業(yè)計(jì)劃（無延遲作業(yè)計(jì)劃（Non-delay schedule） 沒有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃沒有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃 延遲延遲 有工件等待加工時(shí)，機(jī)器出現(xiàn)空閑，即使這段空閑時(shí)間有工件等待加工時(shí)，機(jī)器出現(xiàn)空閑，即使這段空閑時(shí)間不足以完成一道工序不足以完成一道工序 能動(dòng)作業(yè)計(jì)劃和無延遲

31、作業(yè)計(jì)劃的生成方法能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃的生成方法 將每安排一道工序稱作一將每安排一道工序稱作一“步步” 設(shè)設(shè) Stt步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃 Ot第第t步可以排序的工序的集合步可以排序的工序的集合 TkOt中工序中工序Ok的最早可能開工時(shí)間的最早可能開工時(shí)間 TkOt中工序中工序Ok的最早可能完工時(shí)間的最早可能完工時(shí)間 1.能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟 （1）設(shè)）設(shè)t=l，S1為空集，為空集，O1為各工件第一道工序的集為各工件第一道工序的集合合 （2）求）求T*=minTk，并求出，并求出T*出現(xiàn)的機(jī)器出現(xiàn)的機(jī)器M*。如果。如

32、果M*有多臺(tái)，則任選一臺(tái)有多臺(tái)，則任選一臺(tái) （3）從）從Ot中挑出滿足以下兩個(gè)條件的工序中挑出滿足以下兩個(gè)條件的工序Oj：需要機(jī)：需要機(jī)器器M*加工，且加工，且TjT* （4）將確定的工序）將確定的工序Oj放入放入St，從，從Ot沖消去沖消去Oj，并將，并將Oj的緊后工序放入的緊后工序放入Ot，使，使t=t+1 （5）若還有未安排的工序，轉(zhuǎn)步驟（）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止）；否則，停止 ttOkTkT*T*MjO11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,1

33、73877M12,2,151,3,22,3,2778128M21,3,262,3,281313M22,3,2得到加工順序矩陣得到加工順序矩陣：S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32 23 37 77 73 38 813132. 無延遲作業(yè)計(jì)劃的構(gòu)成步驟無延遲作業(yè)計(jì)劃的構(gòu)成步驟 （1）設(shè)）設(shè)t=1，S1為空集，為空集，O1為各工件第一道工序?yàn)楦鞴ぜ谝坏拦ば虻募系募?（2）求）求T*=minTk，并求出，并求出T*出現(xiàn)的機(jī)器出現(xiàn)的機(jī)器M*。如果。如果M*有多臺(tái)；則任選一臺(tái)有多臺(tái)；則任選一

34、臺(tái) （3）從）從Ot中挑出滿足以下兩個(gè)條件的工序中挑出滿足以下兩個(gè)條件的工序Oj：需：需要機(jī)器要機(jī)器M*加工，且加工，且Tj=T* （4）將確定的工序）將確定的工序Oj放入放入St，從，從Ot中消去中消去Oj，并，并將將Oj的緊后工序放入的緊后工序放入Ot，使，使t=t+1 （5）若還有未安排的工序，轉(zhuǎn)步驟；否則，停止）若還有未安排的工序，轉(zhuǎn)步驟；否則，停止 ttOkTkT*T*MjO11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,32,2,1337733M3M11,2,341,3,22,2,173873M12,2,151,3,22,

35、3,27781277M2M22,3,262,3,281312M21,3,2得到加工順序矩陣得到加工順序矩陣：S=1,1,1 2,2,12,3,2 1,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32 23 37 77 73 312121313（二）三類啟發(fā)式算法（二）三類啟發(fā)式算法能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃盡管不一定是最優(yōu)作業(yè)能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃盡管不一定是最優(yōu)作業(yè)計(jì)劃，但一般是較好的作業(yè)計(jì)劃，特別是無延遲作業(yè)計(jì)劃計(jì)劃，但一般是較好的作業(yè)計(jì)劃，特別是無延遲作業(yè)計(jì)劃能提供令人滿意的解。能提供令人滿意的解。一般能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃都有多個(gè)，可用啟一般能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃都有多個(gè)，可用啟發(fā)式方法從中選擇結(jié)果較好的作業(yè)計(jì)劃。發(fā)式方法從中選擇結(jié)果較好的作業(yè)計(jì)劃。一般來說，以構(gòu)成無