生產運作管理chapt11制造業(yè)作業(yè)計劃教案

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

2、生產類型生產控制的特點和“漏斗模型”。教學重點： 1. fmax的計算和n/2/f/fmax問題的最優(yōu)算法（johnson算法）； 2. 能動作業(yè)計劃和無延遲作業(yè)計劃的構成方法11.1作業(yè)計劃問題的基本概念11.1.1基本概念l 編制作業(yè)計劃要解決的問題編制作業(yè)計劃實質上是要將資源分配給不同的任務，按照既定的優(yōu)化目標，確定各種資源利用的時間問題。由于每臺機器都可能被分配了多項任務，而這些任務受到加工路線的約束，就帶來了零件在機器上加工的順序問題。l 有關的名詞術語編制作業(yè)計劃或日程安排(scheduling)排序(sequencing)派工(dispatching)控制(controlling

3、)趕工(expediting) ² “調度”是作業(yè)計劃編制后實施生產控制所采取的一切行動，“編制作業(yè)計劃”是加工制造發(fā)生之前的活動² “機器”，可以是工廠里的各種機床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計算機中央處理單元、存貯器和輸入、輸出單元。一句話，表示“服務者”² “零件”代表“服務對象”。零件可以是單個零件，也可以是一批相同的零件² “加工路線”是零件加工的工藝過程決定的，它是零件加工在技術上的約束 ² “加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題11.1.2假設條件與符號說明

4、為了便于分析研究，有必要做以下假設和符號說明1）一個工件不能同時在幾臺不同的機器上加工2）工件在加工過程中采取平行移動方式，即當上道工序完工后，立即送下道工序加工3）不允許中斷。當一個工件一旦開始加工，必須一直進行到完工，不得中途停止加入其它工件。4）每道工序只在一臺機器上完成5）工件數、機器數和加工時間已知，加工時間與加工順序無關。6）每臺機器同時只能加工一個工件。部分符號：ji工件i，i1，2，nmj機器j，j1，2，mpijji在mj上的加工時間，ji的總加工時間為pipijcmax最長完工時間，cmaxmax ci fmax最長流程時間，fmaxmax fi lmax最長延遲時間，lm

5、axmax li 11.1.3排序問題的分類和表示法排序問題，按照機器、工件和目標函數的特征等，可以進行很多的分類，在我們的課程中我們要求掌握流水作業(yè)排序問題中的最長流程時間最短的計算和單件作業(yè)排序問題 （多機排序又按加工路線的特征分為：單件作業(yè)排序和流水作業(yè)排序問題）表示法：康威用4個參數的排序問題表示法： n/m/a/b 其中，n為工件數；m為機器數； a為車間類型，有“f”類，“p”類，“g”類等。f表示流水作業(yè)排序問題（工件在不同機器上的加工順序不一致），p表示流水作業(yè)排列排序問題（即所有工件在各臺機器上的加工順序都相同的情況），g表示一般單件作業(yè)排序問題；b為目標函數，通常是使其值最

6、小11.2 流水作業(yè)排序問題流水車間(flow shop):工件的加工路線都一致，典型的如流水線11.2.1 最長流程時間的計算 11.2.2 兩臺機器排序問題的最優(yōu)算法 11.2.3 多臺機器排序問題的啟發(fā)式算法11.2.4 相同零件、不同移動方式下加工周期的計算11.2.1 最長流程時間fmax（又稱加工周期）的計算² 最長流程時間fmax（又稱加工周期）是從第一個工件在第一臺機器開始加工時算起，到最后一個工件在最后一臺機器上完成加工時為止所經過的時間。例子 見課本p301例11.1：有一個6/4/p/fmax問題，其加工時間如下表，當按順序s（6，1，5，2，4，3）加工時，求

7、fmax。11.2.2 n/2/f/fmax （兩臺機器流水作業(yè)排序）問題的最優(yōu)算法² 當機器數是2的時候，每個工件都從m1m2的順序加工，也就是n/2/f/fmax問題。對于這個問題，s·m·johnson于1954年提出了一個有效的算法，也就是現在著名的johnson算法。² 約翰森法則：如果min(ai, bj) < min (aj, bi),則工件i應該排在工件j之前。² 約翰森算法：（1）從加工時間矩陣中找出最短加工時間；（2）若最短加工時間出現在機器m1 上，則對應工件應該盡可能往前排；若最短加工時間出現在機器m2 上，則對應

8、工件應該盡可能往后排。然后從加工時間矩陣中劃去已排序工件的加工時間。若最短加工時間有多個，則任挑一個。（3）若所有工件都已排序，停止。否則，轉步驟（1）。例子 見課本p302例11.2² johnson算法的改進算法，步驟1）將所有ai bi的工件按ai值不減的順序排成一個序列a；2）將aibi的工件按bi值不增的順序排成一個序列b；3）將a放到b之前，就構成了一個最優(yōu)加工順序。例子 見課本p303表11-411.2.3 一般n/m/p/ fmax (多臺機器排列排序)問題的啟發(fā)式算法² palmer法（帕爾瑪法）² 關鍵工件法1）計算每個工件的總加工時間，將加工

9、時間最長的工件作為關鍵工件c；2）對于余下的工件，若pi1pim則按pi1不減的順序排成一個序列sa ,若pi1>pim 則按pim不增的順序排成一個序列sb;3）順序（sa,c,sb）即為所求順序。² cds法（johnson算法的擴展應用）11.2.4 相同零件不同移動方式下加工周期的計算² 當n個零件相同，則無排序問題。但不同移動方式下的加工周期不同² 三種典型的移動方式順序移動方式：一批零件全部加工完成后，整批移動到下道工序加工平行移動方式：單個零件加工完成后，立即移動到下道工序加工平行順序移動方式：兩者混合Ø 順序移動方式設零件批量為n（

10、件），工序數目為m，一批零件不計算工序間運輸時間，只考慮加工時間，設其加工的周期為t（分鐘），零件在i道工序的單件工時為 （分鐘/件），i=1.2n. 則該批零件的加工周期為： 例子 見課本p306例11.4Ø 平行移動方式零件平行移動的加工周期為： 例子 見課本p307例11.4Ø 平行順序移動方式特點：既保持一批零件順序加工，有盡可能使相鄰工序加工時間平行進行。具體做法：1） 當ti<ti+1時，零件按平行移動方式轉移；2） 當titi+1時，以i工序最后一個零件的完工時間按為基準，往前推移（n-1）× ti+1作為零件在（i+1）工序的開始加工時間。平

11、行順序移動加工周期計算 例子 見課本p307例11.411.3 單件作業(yè)排序問題11.3.1 問題的描述11.3.2 兩種作業(yè)計劃的構成11.3.3 求解一般n/m/g/fmax問題的啟發(fā)式方法11.3.1 問題的描述² 每一個工件都有自己的加工路線，對每個工件都要進行單獨的排序的問題。² 很多的工件同時在分別在不同的機器上進行各工序的加工。² 那么，單件作業(yè)排序問題就涉及到三個參數：i，j，k。i表示工件號，j表示工序號，k表示機器號，是指完成工件i的第j道工序的機器代號為k。例如，（1，1，1）表示工件1，在第1道工序，在m1上加工。(工件、工序、機器)

12、78; 加工描述矩陣d描述所有工件的加工（每一行描述一個工件的加工，每一列的工序序號相同），與加工時間矩陣t對應d=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2 t=2 4 13 4 511.3.2 兩種作業(yè)計劃的構成l 單件作業(yè)排序問題中，有2個重要的作業(yè)計劃，即：能動作業(yè)計劃和無延遲作業(yè)計劃。² 能動作業(yè)計劃：各工序都按最早可能開（完）工時間來安排；并且保證任何一臺機器的每段空閑時間都不足以加工一道可加工工序的作業(yè)計劃。² 無延遲作業(yè)計劃：各工序都按最早可能開（完）工時間來安排；并且保證有工件等待加工時，沒有任何一臺機器有空閑時間的作業(yè)計劃。l

13、符號說明：每安排一道工序稱為一“步”st:t步之前已排序工序構成的部分作業(yè)計劃；ot:t步可排序工序的集合；tk為ot中工序ok的最早可能開始時間；tk為ot中工序ok的最早可能完成時間。 l 能動作業(yè)計劃的構成步驟（1）設t=1,s1為空集，o1為各工件第一道工序的集合。（2）求t* = mintk,并求出t*所出現的機器m*。如果m*有多臺，則任選一臺。（3）從ot中選出滿足以下兩個條件的工序oj：需要m*加工，且tj< t* 。（4）將選定的工序oj放入st,從ot中消去oj,并將oj的緊后工序放入ot ，使t=t+1.（5）若還有未安排的工序，轉步驟（2）；否則，停止。例子見課本

14、p310例11.5l 無延遲作業(yè)計劃的構成步驟（1）設t=1,s1為空集，o1為各工件第一道工序的集合。（2）求t* = mintk,并求出t*所出現的機器m*。如果m*有多臺，則任選一臺。（3）從ot中選出滿足以下兩個條件的工序oj：需要m*加工，且tj=t* 。（4）將選定的工序oj放入st,從ot中消去oj,并將oj的緊后工序放入ot ，使t=t+1.（5）若還有未安排的工序，轉步驟（2）；否則，停止。例子見課本p312表11-10和圖11-511.3.3 三類啟發(fā)式算法（1）優(yōu)先調度法則² 構成兩種作業(yè)計劃的第（3）步一般都有多道工序可以滿足，按不同的優(yōu)先調度法則來選擇工序，

15、可以得出滿足不同目標函數的作業(yè)計劃² 計算量小² 已經提出100多種優(yōu)先調度法則常用的優(yōu)先調度法則：fcfs（first come, first served）選擇最早進入可排序集合的工序spt( shortest processing time）選擇加工時間最短的工序edd（earliest due date）選擇完工期限最緊的工序scr(smallest critical ratio)選擇臨界比最小的工件mwkr(most work remaining)選擇余下加工時間最長的工件lwkr(least work remaining)選擇余下加工時間最短的工件mopnr(m

16、ost operations remaining)選擇余下工序數最多的工件random 隨機挑選一個工件rush 即緊急訂單或重要顧客優(yōu)先（2）隨機抽樣法² 從全部能動計劃或無延遲計劃中隨機抽樣，得出多個作業(yè)計劃，從中取優(yōu)。² 一般，隨機抽樣法比用優(yōu)先調度法則得到的結果要好一些（3）概率調度法² 將優(yōu)先調度法則與隨機抽樣法結合² 對不同工件將優(yōu)先調度法則分配不同的挑選概率，效果較隨機抽樣法好11.4 生產作業(yè)控制11.4.1實行生產作業(yè)控制的原因和條件11.4.2不同生產類型生產控制的特點11.4.3利用“漏斗模型”進行生產控制11.4.1實行生產作業(yè)控

17、制的原因和條件l 實行生產作業(yè)控制的原因生產計劃在實施的時候容易出現一些偏離，一般是以下的原因：² 加工時間估計不準確² 隨機因素影響² 加工路線的多樣性² 企業(yè)環(huán)境的動態(tài)性當實際情況和計劃出現偏離，就要采取措施，也就是控制問題。l 實施控制的3個條件：² 要有一個標準² 要取得實際生產進度與計劃偏離的信息² 要能采取糾正偏差的行動l 生產作業(yè)控制的程序² 制定生產作業(yè)監(jiān)控體系² 監(jiān)控實際生產過程² 評估偏差情況² 采取糾偏措施l 生產作業(yè)控制的功能² 為每個車間的工單指派優(yōu)

18、先級² 維護車間在制品數量² 將車間工單信息傳送到相應辦公室² 提供實際產出數據來為能力控制服務² 根據車間工單對機位的要求，為在制品庫存管理提供數量信息² 測量人員和設備的效率、利用率和產量。l 生產作業(yè)控制的主要工具實際生產中，有不少工具可以用來進行生產作業(yè)控制，這些工具容易通過運用適當的軟件來生成，主要包括：1) 調度單2) 日報、月報3) 例外報告、異常報告4) 輸入/輸出（input/output control，i/o）報告11.4.2不同生產類型生產控制的特點l 工件生產的提前期可以分成5個部分：移動時間、排隊時間、調整準備時間、加工時間、等待運輸時間。l 單件小批量生產的工件，排隊時間是主要的，所以，控制的主要問題就是排隊的問題。具體的調節(jié)方法通過調節(jié)輸入/輸出，“漏斗模型”能很好地解釋這一控制方法。l 大量大批生產，流水線是自動的，就沒有排隊的問題；一般是通過改變工作班次，調整工作時間、調整工人數量等來控制產量。11.4.3利用