制造業(yè)生產(chǎn)作業(yè)計(jì)劃
第11章　
華中科技大學(xué)管理學(xué)院

生產(chǎn)任務(wù)的最終落實(shí)
MRP確定各車間的零部件投入出產(chǎn)計(jì)劃，將全廠性的產(chǎn)品出產(chǎn)計(jì)劃變成了各車間的生產(chǎn)任務(wù)。
各車間要將車間的生產(chǎn)任務(wù)變成各個(gè)班組、各個(gè)工作地和各個(gè)工人的任務(wù)，才算落到實(shí)處。
將任務(wù)安排到工作地，牽涉到任務(wù)分配和作業(yè)排序問題
編制作業(yè)計(jì)劃要解決的問題
工廠里要對(duì)每個(gè)工人和工作地安排每天的生產(chǎn)任務(wù)，規(guī)定開始時(shí)間和完成時(shí)間；
醫(yī)院要安排病人手術(shù)，為此要安排手術(shù)室、配備手術(shù)器械、手術(shù)醫(yī)師和護(hù)士；
學(xué)校要安排上課時(shí)間表，使學(xué)生能按規(guī)定的時(shí)間到規(guī)定的教室聽事先安排的教師講課。
項(xiàng)目計(jì)劃管理，也是一個(gè)作業(yè)計(jì)劃問題。
英文Scheduling可以譯成編制作業(yè)計(jì)劃或安排日程計(jì)劃(時(shí)間表)。
編制作業(yè)計(jì)劃實(shí)質(zhì)上是要將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時(shí)間問題。
有關(guān)的名詞術(shù)語
排序(Sequencing) 是確定零件在機(jī)器上的加工順序。
編制作業(yè)計(jì)劃(Scheduling)則不僅包括確定加工順序，而且還包括加工任務(wù)的分配和加工每個(gè)零件的開始時(shí)間和完成時(shí)間。
“調(diào)度”是作業(yè)計(jì)劃編制后實(shí)施生產(chǎn)控制所采取的一切行動(dòng)，“編制作業(yè)計(jì)劃”是加工制造發(fā)生之前的活動(dòng)?；疖嚂r(shí)刻表是作業(yè)計(jì)劃。火車時(shí)刻表制定后，對(duì)火車運(yùn)行的安排，包括發(fā)生晚點(diǎn)后的處理，都屬于調(diào)度。
名詞術(shù)語(續(xù))
“派工” (Dispatching)是在作業(yè)計(jì)劃制定以后，按照作業(yè)計(jì)劃的要求，將具體生產(chǎn)任務(wù)通過工票或施工單的形式下達(dá)到具體的機(jī)床和工人，屬于通常所說的“調(diào)度”范圍。
“趕工” (Expediting)是在實(shí)際進(jìn)度已落后于計(jì)劃進(jìn)度時(shí)采取的行動(dòng)，也屬于通常所說的“調(diào)度”范圍。
“機(jī)器”，可以是工廠里的各種機(jī)床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計(jì)算機(jī)中央處理單元、存貯器和輸入、輸出單元。表示“服務(wù)者”；
名詞術(shù)語(續(xù))
“零件”則代表“服務(wù)對(duì)象”。零件可以是單個(gè)零件，也可以是一批相同的零件
“加工路線”是零件加工經(jīng)過不同機(jī)器構(gòu)成的路線。比如，某零件要經(jīng)過車、銑、占、磨的路線加工，我們可以用M1,M2,M3,M4來表示。
“加工順序”則表示每臺(tái)機(jī)器加工n個(gè)零件的先后順序，是排序要解決的問題
4參數(shù)表示法:
　　　　n /m /A /B。 其中, n ──零件數(shù)； m ──機(jī)器數(shù)； A ──作業(yè)類型；在A的位置若標(biāo)以“F”，則代表流水作業(yè)排序問題。若標(biāo)以“P”，則表示流水作業(yè)排列排序問題。若標(biāo)以“G”，則表示一般單件作業(yè)排序問題。當(dāng)m＝1，則A處為空白 B──目標(biāo)函數(shù)，通常是使其值最小。
流水作業(yè)計(jì)劃問題
流水線是流水車間(Flow shop) 典型的代表，每個(gè)零件的加工路線都一致。
只要加工路線一致：M1， M2, M3，…..，Mm,不要求每個(gè)零件都經(jīng)過每臺(tái)機(jī)器加工
最長流程時(shí)間Fmax的計(jì)算
　　最長流程時(shí)間又稱作加工周期 　　6/4/p/ Fmax問題，當(dāng)按順序S＝( 6,1,5,2,4,3)加工時(shí)，求Fmax.

加工周期為46
n/2/F/Fmax問題的最優(yōu)算法
　Johnson算法： 　?、佟募庸r(shí)間矩陣中找出最短的加工時(shí)間。 　?、凇∪糇疃痰募庸r(shí)間出現(xiàn)在M1上，則對(duì)應(yīng)的零件盡可能往前排；若最短加工時(shí)間出現(xiàn)在M2上，則對(duì)應(yīng)零件盡可能往后排。然后，從加工時(shí)間矩陣中劃去已排序零件的加工時(shí)間。若最短加工時(shí)間有多個(gè)，則任挑一個(gè) 　　③　若所有零件都已排序，停止。否則，轉(zhuǎn)步驟①。

求最優(yōu)順序
算法步驟的改進(jìn)
把Johnson算法作些改變，改變后的算法按以下步驟進(jìn)行：
　　①　將所有ai≤bi的零件按ai值不減的順序排成一個(gè)序列A。
　?、凇⑺衋i＞bi的零件按bi值不增的順序排成一個(gè)序列B。
　　③　將A放到B之前，就構(gòu)成了最優(yōu)加工順序

序列A為 (2， 5，6，1)，序列B為(4，3)，構(gòu)成最優(yōu)順序?yàn)?(2，5，6，1， 4，3)，與Johnson算法結(jié)果一致。

Johnson法則只是一個(gè)充分條件，不是必要條件。不符合這個(gè)法則的加工順序，也可能是最優(yōu)順序。如對(duì)例11-2順序(2，5，6，4，1，3)不符合Johnson法則，但它也是一個(gè)最優(yōu)順序 
對(duì)于3臺(tái)機(jī)器的流水車間排序問題，只有幾種特殊類型的問題找到了有效算法。
對(duì)于一般的流水車間排列排序問題，可以用分支定界法。
求一般n/m/P/ Fmax問題近優(yōu)解 (Near optimal solution)的啟發(fā)式算法 　　
關(guān)鍵零件法
CDS法　　

關(guān)鍵零件法求近優(yōu)解舉例
CDS法
Campbell-Dudek-Smith 三人提出了一個(gè)啟發(fā)式算法,簡稱CDS法。他們把Johnson算法用于一般的n/m/P/Fmax問題，得到(ｍ－1)個(gè)加工順序，取其中優(yōu)者

當(dāng)ｌ＝1時(shí)，按Johnson算法得到加工順序(1，2，3，4)； 當(dāng)ｌ＝2時(shí)，得到加工順序(2，3，1，4)。對(duì)于順序(2，3，1， 4)，相應(yīng)的Fmax＝29。所以，取順序(1，2，3，4)。我們已經(jīng)知道，這就是最優(yōu)順序。
單件作業(yè)排序問題
加工描述矩陣和加工時(shí)間矩陣
無延遲作業(yè)計(jì)劃(non-delay schedule)的構(gòu)成

我們稱每安排一道工序稱作一“步”，設(shè)
　　{St}──t步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃；
　　{ Ot }──第t步可以排序的工序的集合；
　　Tk　──{ Ot }中工序Ok的最早可能開工時(shí)間；
Tk’　──{ Ot }中工序Ok的最早可能完工時(shí)間。 

無延遲作業(yè)計(jì)劃的構(gòu)成步驟:
?、佟≡O(shè)t＝1，{S1}為空集，{O1}為各工件第一道工序的集合。 　?、凇∏骉*＝min{Tk}，并求出T*出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)，則任選一臺(tái)。 　?、邸膡Ot}中挑出滿足以下兩個(gè)條件的工序Oj：需要機(jī)器M*加工，且Tj＝T*。 　?、堋⒋_定的工序Oj放入{St}，從{ Ot }中消去Oj，并將Oj的緊后工序放入{ Ot }，使t＝t＋1。 　　⑤　若還有未安排的工序，轉(zhuǎn)步驟②；否則，停止。

優(yōu)先派工法則
在介紹無延遲作業(yè)計(jì)劃的構(gòu)成步驟時(shí)，其中第③步的兩個(gè)條件一般都有多個(gè)工序可以滿足。按什么樣的準(zhǔn)則來選擇可安排的工序，對(duì)作業(yè)計(jì)劃的優(yōu)劣有很大影響。為了得到所希望的作業(yè)計(jì)劃，人們提出了很多優(yōu)先調(diào)度法則，按優(yōu)先調(diào)度法則挑選工序比隨意挑選一道工序的方法更能符合計(jì)劃編制者的要求，同時(shí)又不必列出所有可能的作業(yè)計(jì)劃，從而計(jì)算量小。
迄今，人們已提出了100多個(gè)優(yōu)先調(diào)度法則，其中主要的有下8個(gè)：
　?、佟PT(Shortest Processing Time)法則　優(yōu)先選擇加工時(shí)間最短的工序。
　?、凇CFS(First Come First Served)法則　優(yōu)先選擇最早進(jìn)入可排工序集合的工件。
優(yōu)先派工法則(續(xù))
　?、邸DD(Earliest Due Date)法則　優(yōu)先選擇完工期限緊的工件。
　　④　MWKR(Most Work Remaining)法則　優(yōu)先選擇余下加工時(shí)間最長的工件。
　　⑤　LWKR(Least Work Remaining)法則　優(yōu)先選擇余下加工時(shí)間最短的工件。
　?、蕖OPNR(Most Operations Remaining)法則　優(yōu)先選擇余下工序數(shù)最多的工件。
　?、摺CR(Smallest Critical Ratio)法則　優(yōu)先選擇臨界比最小的工件。臨界比為工件允許停留時(shí)間與工件余下加工時(shí)間之比。
　?、唷ANDOM法則　隨機(jī)地挑一個(gè)工件
隨機(jī)抽樣法
用窮舉法或分支定界法求一般單件車間排序問題的最優(yōu)解時(shí)，實(shí)際上比較了全部能動(dòng)作業(yè)計(jì)劃；采用優(yōu)先調(diào)度法則求近優(yōu)解時(shí)，只選擇了一種作業(yè)計(jì)劃。
　　隨機(jī)抽樣法介于這兩個(gè)極端之間。
它從全部無延遲作業(yè)計(jì)劃之中抽樣，得出多個(gè)作業(yè)計(jì)劃，從中選優(yōu)。
應(yīng)用隨機(jī)抽樣法時(shí)，實(shí)際上是對(duì)同一個(gè)問題多次運(yùn)用RANDOM法則來決定要挑選的工序，從而得到多個(gè)作業(yè)計(jì)劃。
概率調(diào)度法
隨機(jī)抽樣法是從k個(gè)可供選擇的工序以等概率方式挑選，每個(gè)工序被挑選的概率為1／k，這種方法沒有考慮不同工序的特點(diǎn)，有一定盲目性。
例如，在構(gòu)在無延遲作業(yè)計(jì)劃的第③步有3道工序，A、B和C可挑選，這3道工序所需的時(shí)間分別為3，4和7。如果按RANDOM法則，每道工序挑選上的概率都是1／3；如果按SPT法則，則只能挑選工序A?，F(xiàn)按目標(biāo)函數(shù)的要求，選擇了SPT法則。按概率調(diào)度法，將這3道工序按加工時(shí)間從小到大排列，然后給每道工序從大到小分配一個(gè)被挑選的概率，比如A、B和C的挑選概率分別為6／14、5／14和3／14。

制造業(yè)生產(chǎn)作業(yè)計(jì)劃