生產(chǎn)運(yùn)作管理chapt11制造業(yè)作業(yè)計(jì)劃教案

1、第11章 制造業(yè)作業(yè)計(jì)劃與控制Scheduling and Controlling for Manufacturing11.1 作業(yè)計(jì)劃問題的基本概念11.2 流水作業(yè)排序問題11.3 單件作業(yè)的排序問題11.4 生產(chǎn)作業(yè)控制 教學(xué)要求： 1. 了解排序問題的術(shù)語、假設(shè)條件基本符號、分類和表示法； 2. 掌握流水作業(yè)排序問題最長流程時(shí)間Fmax的計(jì)算和n/2/F/Fmax問題的最優(yōu)算法，理解n/2/P/Fmax問題的啟發(fā)式算法；理解相同零件不同移動(dòng)方式下加工周期的計(jì)算； 3. 掌握單件作業(yè)排序問題的能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃及其構(gòu)成方法，理解三類啟發(fā)式算法； 4. 了解生產(chǎn)作業(yè)控制，理解不同

2、生產(chǎn)類型生產(chǎn)控制的特點(diǎn)和“漏斗模型”。教學(xué)重點(diǎn)： 1. Fmax的計(jì)算和n/2/F/Fmax問題的最優(yōu)算法（Johnson算法）； 2. 能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃的構(gòu)成方法11.1作業(yè)計(jì)劃問題的基本概念基本概念l 編制作業(yè)計(jì)劃要解決的問題編制作業(yè)計(jì)劃實(shí)質(zhì)上是要將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時(shí)間問題。由于每臺機(jī)器都可能被分配了多項(xiàng)任務(wù)，而這些任務(wù)受到加工路線的約束，就帶來了零件在機(jī)器上加工的順序問題。l 有關(guān)的名詞術(shù)語編制作業(yè)計(jì)劃或日程安排(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)趕工(Ex

3、pediting) “調(diào)度”是作業(yè)計(jì)劃編制后實(shí)施生產(chǎn)控制所采取的一切行動(dòng)，“編制作業(yè)計(jì)劃”是加工制造發(fā)生之前的活動(dòng) “機(jī)器”，可以是工廠里的各種機(jī)床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計(jì)算機(jī)中央處理單元、存貯器和輸入、輸出單元。一句話，表示“服務(wù)者” “零件”代表“服務(wù)對象”。零件可以是單個(gè)零件，也可以是一批相同的零件 “加工路線”是零件加工的工藝過程決定的，它是零件加工在技術(shù)上的約束 “加工順序”則表示每臺機(jī)器加工n個(gè)零件的先后順序，是排序和編制作業(yè)計(jì)劃要解決的問題假設(shè)條件與符號說明為了便于分析研究，有必要做以下假設(shè)和符號說明1）一個(gè)工件不能同時(shí)在幾臺不同的機(jī)器上加工2

4、）工件在加工過程中采取平行移動(dòng)方式，即當(dāng)上道工序完工后，立即送下道工序加工3）不允許中斷。當(dāng)一個(gè)工件一旦開始加工，必須一直進(jìn)行到完工，不得中途停止加入其它工件。4）每道工序只在一臺機(jī)器上完成5）工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無關(guān)。6）每臺機(jī)器同時(shí)只能加工一個(gè)工件。部分符號：Ji工件i，i1，2，nMj機(jī)器j，j1，2，mpijJi在Mj上的加工時(shí)間，Ji的總加工時(shí)間為PipijCmax最長完工時(shí)間，Cmaxmax Ci Fmax最長流程時(shí)間，F(xiàn)maxmax Fi Lmax最長延遲時(shí)間，Lmaxmax Li 排序問題的分類和表示法排序問題，按照機(jī)器、工件和目標(biāo)函數(shù)的特征等，可以

5、進(jìn)行很多的分類，在我們的課程中我們要求掌握流水作業(yè)排序問題中的最長流程時(shí)間最短的計(jì)算和單件作業(yè)排序問題 （多機(jī)排序又按加工路線的特征分為：單件作業(yè)排序和流水作業(yè)排序問題）表示法：康威用4個(gè)參數(shù)的排序問題表示法： n/m/A/B 其中，n為工件數(shù)；m為機(jī)器數(shù)； A為車間類型，有“F”類，“P”類，“G”類等。F表示流水作業(yè)排序問題（工件在不同機(jī)器上的加工順序不一致），P表示流水作業(yè)排列排序問題（即所有工件在各臺機(jī)器上的加工順序都相同的情況），G表示一般單件作業(yè)排序問題；B為目標(biāo)函數(shù)，通常是使其值最小11.2 流水作業(yè)排序問題流水車間(Flow shop):工件的加工路線都一致，典型的如流水線 最

6、長流程時(shí)間的計(jì)算 兩臺機(jī)器排序問題的最優(yōu)算法 多臺機(jī)器排序問題的啟發(fā)式算法 相同零件、不同移動(dòng)方式下加工周期的計(jì)算 最長流程時(shí)間Fmax（又稱加工周期）的計(jì)算 最長流程時(shí)間Fmax（又稱加工周期）是從第一個(gè)工件在第一臺機(jī)器開始加工時(shí)算起，到最后一個(gè)工件在最后一臺機(jī)器上完成加工時(shí)為止所經(jīng)過的時(shí)間。例子 見課本P301例11.1：有一個(gè)6/4/p/Fmax問題，其加工時(shí)間如下表，當(dāng)按順序S（6，1，5，2，4，3）加工時(shí)，求Fmax。 n/2/F/Fmax （兩臺機(jī)器流水作業(yè)排序）問題的最優(yōu)算法 當(dāng)機(jī)器數(shù)是2的時(shí)候，每個(gè)工件都從M1M2的順序加工，也就是n/2/F/Fmax問題。對于這個(gè)問題，SM

7、Johnson于1954年提出了一個(gè)有效的算法，也就是現(xiàn)在著名的Johnson算法。 約翰森法則：如果Min(ai, bj) pim 則按pim不增的順序排成一個(gè)序列Sb;3）順序（Sa,C,Sb）即為所求順序。 CDS法（Johnson算法的擴(kuò)展應(yīng)用）11.2.4 相同零件不同移動(dòng)方式下加工周期的計(jì)算 當(dāng)n個(gè)零件相同，則無排序問題。但不同移動(dòng)方式下的加工周期不同 三種典型的移動(dòng)方式順序移動(dòng)方式：一批零件全部加工完成后，整批移動(dòng)到下道工序加工平行移動(dòng)方式：單個(gè)零件加工完成后，立即移動(dòng)到下道工序加工平行順序移動(dòng)方式：兩者混合 順序移動(dòng)方式設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)算工序間運(yùn)

8、輸時(shí)間，只考慮加工時(shí)間，設(shè)其加工的周期為T（分鐘），零件在i道工序的單件工時(shí)為 （分鐘/件），i=1.2n. 則該批零件的加工周期為： 例子 見課本P306例11.4 平行移動(dòng)方式零件平行移動(dòng)的加工周期為： 例子 見課本P307例11.4 平行順序移動(dòng)方式特點(diǎn)：既保持一批零件順序加工，有盡可能使相鄰工序加工時(shí)間平行進(jìn)行。具體做法：1） 當(dāng)titi+1時(shí)，零件按平行移動(dòng)方式轉(zhuǎn)移；2） 當(dāng)titi+1時(shí)，以i工序最后一個(gè)零件的完工時(shí)間按為基準(zhǔn)，往前推移（n-1） ti+1作為零件在（i+1）工序的開始加工時(shí)間。平行順序移動(dòng)加工周期計(jì)算 例子 見課本P307例11.411.3 單件作業(yè)排序問題 問題

9、的描述 兩種作業(yè)計(jì)劃的構(gòu)成 求解一般n/m/G/Fmax問題的啟發(fā)式方法 問題的描述 每一個(gè)工件都有自己的加工路線，對每個(gè)工件都要進(jìn)行單獨(dú)的排序的問題。 很多的工件同時(shí)在分別在不同的機(jī)器上進(jìn)行各工序的加工。 那么，單件作業(yè)排序問題就涉及到三個(gè)參數(shù)：i，j，k。i表示工件號，j表示工序號，k表示機(jī)器號，是指完成工件i的第j道工序的機(jī)器代號為k。例如，（1，1，1）表示工件1，在第1道工序，在M1上加工。(工件、工序、機(jī)器) 加工描述矩陣D描述所有工件的加工（每一行描述一個(gè)工件的加工，每一列的工序序號相同），與加工時(shí)間矩陣T對應(yīng)D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,

10、2 T=2 4 13 4 5 兩種作業(yè)計(jì)劃的構(gòu)成l 單件作業(yè)排序問題中，有2個(gè)重要的作業(yè)計(jì)劃，即：能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃。 能動(dòng)作業(yè)計(jì)劃：各工序都按最早可能開（完）工時(shí)間來安排；并且保證任何一臺機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序的作業(yè)計(jì)劃。 無延遲作業(yè)計(jì)劃：各工序都按最早可能開（完）工時(shí)間來安排；并且保證有工件等待加工時(shí)，沒有任何一臺機(jī)器有空閑時(shí)間的作業(yè)計(jì)劃。l 符號說明：每安排一道工序稱為一“步”St:t步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃；Ot:t步可排序工序的集合；Tk為Ot中工序Ok的最早可能開始時(shí)間；Tk為Ot中工序Ok的最早可能完成時(shí)間。 l 能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟（

11、1）設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺，則任選一臺。（3）從Ot中選出滿足以下兩個(gè)條件的工序Oj：需要M*加工，且Tj T* 。（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。例子見課本P310例11.5l 無延遲作業(yè)計(jì)劃的構(gòu)成步驟（1）設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺，則任選一臺。（3）從Ot中選出滿足以下兩個(gè)條件的

12、工序Oj：需要M*加工，且Tj=T* 。（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。例子見課本P312表11-10和圖11-5 三類啟發(fā)式算法（1）優(yōu)先調(diào)度法則 構(gòu)成兩種作業(yè)計(jì)劃的第（3）步一般都有多道工序可以滿足，按不同的優(yōu)先調(diào)度法則來選擇工序，可以得出滿足不同目標(biāo)函數(shù)的作業(yè)計(jì)劃 計(jì)算量小 已經(jīng)提出100多種優(yōu)先調(diào)度法則常用的優(yōu)先調(diào)度法則：FCFS（first come, first served）選擇最早進(jìn)入可排序集合的工序SPT( shortest processing time）選擇加

13、工時(shí)間最短的工序EDD（earliest due date）選擇完工期限最緊的工序SCR(smallest critical ratio)選擇臨界比最小的工件MWKR(most work remaining)選擇余下加工時(shí)間最長的工件LWKR(least work remaining)選擇余下加工時(shí)間最短的工件MOPNR(most operations remaining)選擇余下工序數(shù)最多的工件RANDOM 隨機(jī)挑選一個(gè)工件Rush 即緊急訂單或重要顧客優(yōu)先（2）隨機(jī)抽樣法 從全部能動(dòng)計(jì)劃或無延遲計(jì)劃中隨機(jī)抽樣，得出多個(gè)作業(yè)計(jì)劃，從中取優(yōu)。 一般，隨機(jī)抽樣法比用優(yōu)先調(diào)度法則得到的結(jié)果要好一些

14、（3）概率調(diào)度法 將優(yōu)先調(diào)度法則與隨機(jī)抽樣法結(jié)合 對不同工件將優(yōu)先調(diào)度法則分配不同的挑選概率，效果較隨機(jī)抽樣法好11.4 生產(chǎn)作業(yè)控制實(shí)行生產(chǎn)作業(yè)控制的原因和條件不同生產(chǎn)類型生產(chǎn)控制的特點(diǎn)利用“漏斗模型”進(jìn)行生產(chǎn)控制實(shí)行生產(chǎn)作業(yè)控制的原因和條件l 實(shí)行生產(chǎn)作業(yè)控制的原因生產(chǎn)計(jì)劃在實(shí)施的時(shí)候容易出現(xiàn)一些偏離，一般是以下的原因： 加工時(shí)間估計(jì)不準(zhǔn)確 隨機(jī)因素影響 加工路線的多樣性 企業(yè)環(huán)境的動(dòng)態(tài)性當(dāng)實(shí)際情況和計(jì)劃出現(xiàn)偏離，就要采取措施，也就是控制問題。l 實(shí)施控制的3個(gè)條件： 要有一個(gè)標(biāo)準(zhǔn) 要取得實(shí)際生產(chǎn)進(jìn)度與計(jì)劃偏離的信息 要能采取糾正偏差的行動(dòng)l 生產(chǎn)作業(yè)控制的程序 制定生產(chǎn)作業(yè)監(jiān)控體系 監(jiān)控

15、實(shí)際生產(chǎn)過程 評估偏差情況 采取糾偏措施l 生產(chǎn)作業(yè)控制的功能 為每個(gè)車間的工單指派優(yōu)先級 維護(hù)車間在制品數(shù)量 將車間工單信息傳送到相應(yīng)辦公室 提供實(shí)際產(chǎn)出數(shù)據(jù)來為能力控制服務(wù) 根據(jù)車間工單對機(jī)位的要求，為在制品庫存管理提供數(shù)量信息 測量人員和設(shè)備的效率、利用率和產(chǎn)量。l 生產(chǎn)作業(yè)控制的主要工具實(shí)際生產(chǎn)中，有不少工具可以用來進(jìn)行生產(chǎn)作業(yè)控制，這些工具容易通過運(yùn)用適當(dāng)?shù)能浖砩?，主要包括?) 調(diào)度單2) 日報(bào)、月報(bào)3) 例外報(bào)告、異常報(bào)告4) 輸入/輸出（Input/output control，I/O）報(bào)告不同生產(chǎn)類型生產(chǎn)控制的特點(diǎn)l 工件生產(chǎn)的提前期可以分成5個(gè)部分：移動(dòng)時(shí)間、排隊(duì)時(shí)間、

16、調(diào)整準(zhǔn)備時(shí)間、加工時(shí)間、等待運(yùn)輸時(shí)間。l 單件小批量生產(chǎn)的工件，排隊(duì)時(shí)間是主要的，所以，控制的主要問題就是排隊(duì)的問題。具體的調(diào)節(jié)方法通過調(diào)節(jié)輸入/輸出，“漏斗模型”能很好地解釋這一控制方法。l 大量大批生產(chǎn)，流水線是自動(dòng)的，就沒有排隊(duì)的問題；一般是通過改變工作班次，調(diào)整工作時(shí)間、調(diào)整工人數(shù)量等來控制產(chǎn)量。利用“漏斗模型”進(jìn)行生產(chǎn)控制l 模型介紹 德國漢諾威大學(xué)的Bechte和Wiendall等人于20世紀(jì)80年代初在實(shí)施輸入/輸出控制時(shí)提出了漏斗模型（Funnel Model）。 漏斗模型的基本原則：工作中心的輸入永遠(yuǎn)不能超過工作中心的輸出。當(dāng)工作中心的輸入超過輸出，就會(huì)拖欠訂單，結(jié)果將會(huì)出現(xiàn)作業(yè)推遲、客戶不滿、下游作業(yè)或相關(guān)作業(yè)的延期。l 控制規(guī)則在一段較長的時(shí)間內(nèi)（如數(shù)周）內(nèi)，若工況穩(wěn)定，輸入輸出兩條曲線可以近似地用兩條直線來表示，其斜率（平均生產(chǎn)率）等于平均在制品庫存/平均通過時(shí)間實(shí)際實(shí)踐中，可以采用四個(gè)規(guī)則來調(diào)整輸入、輸出、在制品庫存和通過時(shí)間： 若希望保持在制品庫存量，可暫時(shí)增加或減少輸入。 若希望