第12講 作業(yè)計(jì)劃

1、第12講 作業(yè)計(jì)劃生產(chǎn)作業(yè)計(jì)劃概述作業(yè)排序的數(shù)學(xué)方法 服務(wù)業(yè)的作業(yè)排序第一節(jié) 生產(chǎn)作業(yè)計(jì)劃概述一、生產(chǎn)作業(yè)計(jì)劃的概念 生產(chǎn)作業(yè)計(jì)劃是根據(jù)MRP（物料需求計(jì)劃）下達(dá)的生產(chǎn)任務(wù)，具體、詳細(xì)地規(guī)定了各車間、工段、班組以至每個(gè)工作地在相應(yīng)時(shí)間內(nèi)的生產(chǎn)運(yùn)作任務(wù)和加工順序。二、排序的分類二、排序的分類v 按排序的基本形式分：按排序的基本形式分：勞動(dòng)力排序勞動(dòng)力排序確定人員工作開始與結(jié)束時(shí)間確定人員工作開始與結(jié)束時(shí)間生產(chǎn)作業(yè)排序生產(chǎn)作業(yè)排序工件加工順序或人員工作分配工件加工順序或人員工作分配v 按機(jī)器的種類和數(shù)量分：按機(jī)器的種類和數(shù)量分：?jiǎn)闻_(tái)機(jī)器單臺(tái)機(jī)器多臺(tái)機(jī)器多臺(tái)機(jī)器流水型排序流水型排序非流水型排序非流水

2、型排序v 按預(yù)期目標(biāo)分：按預(yù)期目標(biāo)分：平均流程時(shí)間最短平均流程時(shí)間最短誤期完工的工件最少誤期完工的工件最少v 按工件到達(dá)車間的情況分：按工件到達(dá)車間的情況分：靜態(tài)排序靜態(tài)排序動(dòng)態(tài)排序動(dòng)態(tài)排序三、作業(yè)排序的一般方法 （一）（一）甘特圖甘特圖 甘特圖是作業(yè)排序中最常用的一種工具。它是由亨利勞倫斯甘特(Henry L.Gantt)在1917年首先提出來的。甘特是泰勒創(chuàng)立和推廣科學(xué)管理制度的親密的合作者，也是科學(xué)管理運(yùn)動(dòng)的先驅(qū)者之一。機(jī)械制造工廠作業(yè)進(jìn)度甘特圖機(jī)械制造工廠作業(yè)進(jìn)度甘特圖機(jī)械制造工廠作業(yè)機(jī)械制造工廠作業(yè)機(jī)器機(jī)器甘特圖甘特圖（二）排序的優(yōu)先規(guī)則 (1) FCFS(first come fi

3、rst serve，先到先服務(wù))：按訂單送到的先后順序進(jìn)行加工。 (2) SPT(smallest processing time，最短作業(yè)時(shí)間)：加工時(shí)間最短的作業(yè)首先進(jìn)行，然后是加工時(shí)間第二短的，以此類推。 (3) EDD(earliest due date，最早交貨期)最早交貨期最早加工。將交貨期最早的作業(yè)放在第一個(gè)進(jìn)行。 (4) STR(剩余松弛時(shí)間)：STR是交貨期前所剩余時(shí)間減去剩余的加工時(shí)間所得的差值。 (5) STR/OP(每個(gè)作業(yè)剩余的松弛時(shí)間)：STR/OP最短的任務(wù)最先進(jìn)行。 (6) CR(關(guān)鍵比率)：關(guān)鍵比率是用交貨日期減去當(dāng)前日期的差值除以剩余的工作日數(shù)。關(guān)鍵比率最小

4、的任務(wù)先執(zhí)行。 (7) LCFS(后到先服務(wù))：該規(guī)則經(jīng)常作為默認(rèn)規(guī)則使用。因?yàn)楹髞淼墓畏旁谙葋淼纳厦?，操作員通常是先加工上面的工單。 (8) 隨機(jī)次序第二節(jié)作業(yè)排序的數(shù)學(xué)方法第二節(jié)作業(yè)排序的數(shù)學(xué)方法 作業(yè)排序的表示方法作業(yè)排序的表示方法單臺(tái)設(shè)備上的作業(yè)排序方法單臺(tái)設(shè)備上的作業(yè)排序方法 流水生產(chǎn)線作業(yè)排序方法流水生產(chǎn)線作業(yè)排序方法 單件生產(chǎn)任務(wù)分配與作業(yè)排序單件生產(chǎn)任務(wù)分配與作業(yè)排序一、作業(yè)排序的表示方法 Conway等人提出了可用4個(gè)描述作業(yè)的排序問題， 即：n/m/A/B。其中： n：工件數(shù) m：機(jī)器數(shù) A：排序的類型，可用F、P和G表示。F表示流水型，指所有工件的工藝過程均相同；P表示

5、流水型且為同順序排序，指所有工件的工藝過程均相同，且在每臺(tái)設(shè)備上所有工件的投產(chǎn)順序也必須相同；表示非流水型排序。 B：具體的目標(biāo)。如Fmax為最大的流程時(shí)間最短。 例如，n/5/P/Fmax則表示工件數(shù)為n、機(jī)器數(shù)為5、同順序流水型排序，其目標(biāo)是最大的流程時(shí)間最短。二、單臺(tái)設(shè)備上的作業(yè)排序方法二、單臺(tái)設(shè)備上的作業(yè)排序方法排序規(guī)則： 先到先服務(wù)先到先服務(wù)FCF First-Come, First-Serve 交貨期最早交貨期最早EDD Earliest Due Date 最短加工時(shí)間最短加工時(shí)間 SPT Smallest processing time【范例1】有6個(gè)工件需要在某臺(tái)設(shè)備上加工，各

6、工件的加工時(shí)間如圖1-1所示（工件編號(hào)是工件達(dá)到工作地的先后次序）（當(dāng)前日期為1） 表表1-1 工件的加工時(shí)間與交貨期工件的加工時(shí)間與交貨期工件編號(hào)i123456加工時(shí)間交貨期7148121020210515618 表表1-2 按照先來先加工的規(guī)則排序按照先來先加工的規(guī)則排序注：總的拖期數(shù)是注：總的拖期數(shù)是5件，平均拖期時(shí)間為：件，平均拖期時(shí)間為：（0+3+5+17+17+20）/6=10.33,平均流程時(shí)間：平均流程時(shí)間：(7+15+25+27+32+38)/6=24作業(yè)排序工件編號(hào)112233445566加工時(shí)間等待時(shí)間完成時(shí)間交貨期拖期時(shí)間707140871512310152520522

7、5271017527321517632381820FCFS-先到先服務(wù)先到先服務(wù)二、流水生產(chǎn)線作業(yè)排序方法二、流水生產(chǎn)線作業(yè)排序方法流水線排序問題的描述流水線排序問題的描述 多工件兩臺(tái)設(shè)備的排序問題算法多工件兩臺(tái)設(shè)備的排序問題算法多工件多設(shè)備的排序問題算法多工件多設(shè)備的排序問題算法1.流水線排序問題的描述流水線排序問題的描述假設(shè)：（1）一個(gè)工件不能同時(shí)在不同機(jī)器上加工。（2）工件在加工過程中采用平行移動(dòng)方式（當(dāng)上一道工序完成后立即進(jìn)入下道工序）。（3）不允許中斷，工件一旦進(jìn)入加工狀態(tài)，一直加工完成為止，中途不插入其他工件。（4）每道工序只在一臺(tái)設(shè)備上加工。（5）工件數(shù)、機(jī)器數(shù)與加工時(shí)間已知。2

8、. 多工件兩臺(tái)設(shè)備的排序問題算法多工件兩臺(tái)設(shè)備的排序問題算法 約翰遜法是作業(yè)排序中比較常用的一種排序方法，解決n/2/P/Fmax的排序問題。 它適用的條件是：n個(gè)工件經(jīng)過兩臺(tái)設(shè)備(有限臺(tái)設(shè)備)加工，所有工件在有限設(shè)備上加工的次序相同。 約翰遜法操作步驟： (1) 選出最短加工時(shí)間i，若最短加工時(shí)間有多個(gè)，任選1個(gè)； (2) 若i出現(xiàn)在機(jī)床1，它對(duì)應(yīng)的工件先安排加工，否則放在最后安排，安排后劃去該工件； (3) 重復(fù)上兩個(gè)步驟，直到所有工件都排序完畢。零 件(i)作業(yè)時(shí)間tix機(jī)器1(j)機(jī)器2(k)A52B36C75D43E64【范例2】 有5個(gè)工件在2臺(tái)設(shè)備上加工，加工順序相同，先在設(shè)備1

9、上加工，再在設(shè)備2上加工，工時(shí)列于表1中，用約翰遜法排序。表2 加工工時(shí)表 表表3 零件加工順序表零件加工順序表步 驟加工順序1A2BA3BDA4BEDA5BCEDA零 件BCEDA機(jī)器13/37/106/164/205/25機(jī)器26/95/154/203/232/27表4 零件加工時(shí)間表課堂練習(xí) 已經(jīng)有6個(gè)工件需要在兩臺(tái)設(shè)備上加工的流水作業(yè)，單件加工時(shí)間矩陣如表所示。應(yīng)用Johnson算法確定最優(yōu)解。加工時(shí)間矩陣加工時(shí)間矩陣1234568342761932105i1 ip2ip課堂練習(xí) 表中的第2步，由于最小時(shí)間是2，有兩種可選的方案，即先選工件2和先選工件5，最后得出兩種不同的排序結(jié)果：4

10、36152 或436125。 兩種排序的最長(zhǎng)流程時(shí)間都是35。故兩種排序都是最優(yōu)的排序。3.多工件多設(shè)備的排序問題的算法多工件多設(shè)備的排序問題的算法 CDS法 CDSCDS法是由法是由CambelCambel、DudekDudek、SmithSmith三人合三人合作創(chuàng)立的作創(chuàng)立的Johnson算法的擴(kuò)展方法。 這種方法的基本思想是把多設(shè)備的排序 問題轉(zhuǎn)化為兩臺(tái)設(shè)備的排序問題，然后 利用Johnson算法排序。CDS法的解題步驟 基本步驟：基本步驟： 1 1） 將第將第1 1臺(tái)設(shè)備與第臺(tái)設(shè)備與第m m臺(tái)設(shè)備的工件加工時(shí)間組成兩組加臺(tái)設(shè)備的工件加工時(shí)間組成兩組加工時(shí)間，應(yīng)用工時(shí)間，應(yīng)用Johnso

11、nJohnson算法得出一個(gè)排序方案。算法得出一個(gè)排序方案。 2 2）將第）將第1 1、第、第2 2臺(tái)設(shè)備的工件加工時(shí)間相加臺(tái)設(shè)備的工件加工時(shí)間相加 ，第（，第（m-1m-1）和第和第m m臺(tái)設(shè)備的工件加工時(shí)間相加臺(tái)設(shè)備的工件加工時(shí)間相加 ，組成兩組加工時(shí)間，組成兩組加工時(shí)間，用用JohnsonJohnson算法得出第算法得出第2 2個(gè)排序方案。個(gè)排序方案。 3）重復(fù)上述做法，直到將第）重復(fù)上述做法，直到將第1臺(tái)設(shè)備的加工時(shí)間至第臺(tái)設(shè)備的加工時(shí)間至第(m-1)臺(tái)設(shè)備的加工時(shí)間相加，第臺(tái)設(shè)備的加工時(shí)間相加，第2臺(tái)設(shè)備至第臺(tái)設(shè)備至第m臺(tái)設(shè)備的工臺(tái)設(shè)備的工件加工時(shí)間相加，組成兩組加工時(shí)間，利用件加工

12、時(shí)間相加，組成兩組加工時(shí)間，利用Johnson算算法得到第（法得到第（m-1）個(gè)排序方案。）個(gè)排序方案。 4）在所有的）在所有的(m-1)個(gè)排序方案中選擇流程時(shí)間最短的一個(gè)，個(gè)排序方案中選擇流程時(shí)間最短的一個(gè)，即為所求即為所求。CDS法案例 【范例3】已知有4個(gè)工件在3個(gè)機(jī)器上作業(yè)，見表4，求最優(yōu)工作排序。 用用CDS法求最優(yōu)加工順序。法求最優(yōu)加工順序。 表4 加工時(shí)間表工 件設(shè) 備1234Pi11363Pi28429Pi34582CDS法法-窮舉方案表5 CDS法的方案第一步，取首末兩道工序的時(shí)間構(gòu)成一個(gè)2行矩陣，用約翰遜法排序，即方案1，排序?yàn)?1-2-3-4)，F(xiàn)max=28，計(jì)算過程見

13、表6。表表6 方案方案1的加工時(shí)間的加工時(shí)間表表7 方案方案2的加工時(shí)間的加工時(shí)間第二步，取首兩道工序和尾兩道工序的和，組成一個(gè)新的2行矩陣，用約翰遜法排序，即方案2，排序?yàn)?2-3-1-4)，F(xiàn)max30，計(jì)算過程見表7。（三）單件生產(chǎn)作業(yè)任務(wù)分配與排序（三）單件生產(chǎn)作業(yè)任務(wù)分配與排序1. 任務(wù)分配任務(wù)分配2. 作業(yè)排序作業(yè)排序 1. 任務(wù)分配任務(wù)分配 假設(shè)有n份任務(wù)要分配給n個(gè)任務(wù)承擔(dān)者（人或機(jī)器），用0-1整數(shù)規(guī)劃方法表示，任務(wù)分配問題的數(shù)學(xué)模型為： 式中： 為第 個(gè)任務(wù)承擔(dān)者完成第 個(gè)任務(wù)的時(shí)間（或費(fèi)用）。 ninjijijxcZ11minijcij1. 任務(wù)分配（續(xù)）任務(wù)分配（續(xù)）約

14、束條件： （1） （2） （3）系數(shù)矩陣：niijx11nj,2, 111njijxni,2, 11, 0 orxijnnnnnnijcccccccccc212222111211)(【范例4】 現(xiàn)將某種產(chǎn)品的4個(gè)零件，分配給4個(gè)班組分別去完成。一個(gè)小組承擔(dān)一個(gè)零件，不同小組完成這一零件的作業(yè)時(shí)間見表8，求怎樣分配任務(wù)所花時(shí)間最少。表8 作業(yè)時(shí)間表 天 解題過程見：P346課堂練習(xí) 有四項(xiàng)任務(wù)要在4個(gè)設(shè)備上加工，加工時(shí)間如表所示。確定最優(yōu)化的任務(wù)分配方案。 表表9-任務(wù)加工時(shí)間任務(wù)加工時(shí)間任務(wù)設(shè)備J1J2J3J4任務(wù)設(shè)備J1J2J3J4M135710M35738M242148M4849112.

15、單件車間排序單件車間排序單件生產(chǎn)作業(yè)排序問題是最復(fù)雜的一類排序問題。單件車間作業(yè)計(jì)劃與流水車間的作業(yè)計(jì)劃不同，由于工件的加工路線多樣化，導(dǎo)致其作業(yè)排序的問題比流水作業(yè)排序問題復(fù)雜得多。用優(yōu)化方法需要更長(zhǎng)計(jì)算時(shí)間，因此一般也都用啟發(fā)方法才更有實(shí)踐應(yīng)用價(jià)值第三節(jié) 服務(wù)作業(yè)排序 服務(wù)運(yùn)作的特點(diǎn) 顧客排序 服務(wù)人員排序一、一、服務(wù)運(yùn)作的特征服務(wù)運(yùn)作的特征同步性同步性(simultaneity)(simultaneity)，服務(wù)過程中的顧客參與。，服務(wù)過程中的顧客參與。異質(zhì)性異質(zhì)性(heterogeneity)(heterogeneity)，服務(wù)難以標(biāo)準(zhǔn)化。，服務(wù)難以標(biāo)準(zhǔn)化。易逝性易逝性(perisha

16、bility)(perishability)，服務(wù)不能通過庫(kù)存來調(diào)，服務(wù)不能通過庫(kù)存來調(diào)節(jié)能力。節(jié)能力。二、顧客排序二、顧客排序q預(yù)約預(yù)約q預(yù)訂預(yù)訂q排隊(duì)等待排隊(duì)等待三三、 服務(wù)員服務(wù)員排序排序-輪班輪班 將服務(wù)員工安排到不同的服務(wù)需求時(shí)間上的作業(yè)計(jì)劃是服務(wù)員工輪班問題。 下面介紹兩種常見的輪班方式： 1. 員工固定的輪班計(jì)劃 2. 員工變化的輪班計(jì)劃。1. 員工固定的輪班計(jì)劃員工固定的輪班計(jì)劃 (1) 三班制:班次第一周第二周第三周第四周早甲乙丙甲中乙丙甲乙夜丙甲乙丙表表10 10 三班倒的輪班計(jì)劃三班倒的輪班計(jì)劃(2)四班制:即“四班三運(yùn)轉(zhuǎn)” 輪班方式工作日1234567891011121

17、3141516工作班組早班甲甲丁丁丙丙乙乙甲甲丁丁丙丙乙乙中班乙乙甲甲丁丁丙丙乙乙甲甲丁丁丙丙夜班丙丙乙乙甲甲丁丁丙丙乙乙甲甲丁丁輪休班組丁丁丙丙乙乙甲甲丁丁丙丙乙乙甲甲表表11 11 四班三運(yùn)轉(zhuǎn)的輪班計(jì)劃四班三運(yùn)轉(zhuǎn)的輪班計(jì)劃2. 員工變化的輪班計(jì)劃員工變化的輪班計(jì)劃 員工上班人數(shù)變化的工作輪班計(jì)劃是每個(gè)人沒有固定的工作班組，每個(gè)時(shí)間段的上崗人員也不固定，隨需求的變化而變化。 員工上班人數(shù)變化的工作輪班方式很多,有日工作制與小時(shí)工作制等,解決排班的方法主要有如下兩種: （1）啟發(fā)方法:如循環(huán)排序法 （2）最優(yōu)化方法:如線性規(guī)劃法（1）循環(huán)排序法循環(huán)排序法 循環(huán)排序法是一種既簡(jiǎn)單又實(shí)用的啟發(fā)式方

18、法，其基本步驟如下： 步驟步驟1：從每周的員工需求人數(shù)中找到所需員工數(shù)量之和最小的連續(xù)兩個(gè)工作日,安排一名員工在這兩天中休息。步驟步驟2：使該兩天的需求人數(shù)保持不變使該兩天的需求人數(shù)保持不變, 其他日期的需其他日期的需求人數(shù)減求人數(shù)減1(如果是如果是0不變不變)步驟步驟3：在新一行中找出所需員工數(shù)量最少的連續(xù)兩天，并再次循環(huán)。將下一名員工分配到剩余的工作日中。步驟步驟4：重復(fù)上述過程（步驟2和3），直到所有的人員需求得到滿足?！痉独?】某醫(yī)院擬根據(jù)一周內(nèi)病人每天就醫(yī)數(shù)量不均衡的情況，確定護(hù)士的數(shù)量及排班計(jì)劃。要求每名護(hù)士每周工作5天，并連續(xù)休息2天。每天所需的護(hù)士數(shù)量如表12所示。表12 護(hù)士需求數(shù)量一覽表解：循環(huán)排序法從連續(xù)2天所需護(hù)士數(shù)量最少的日期確定護(hù)士的休息日，其他的為工作日，并以此類推，排出每名護(hù)士工作與休息計(jì)劃。本例，星期六和星期日所需護(hù)士最少，故護(hù)士一被安排到這兩天休息，星期一至星期五工作。因此，星期一至星期五所需的護(hù)士數(shù)在原護(hù)士需求數(shù)量的基礎(chǔ)上減1，星期六和星期日數(shù)量不變（因護(hù)士一休息），這兩個(gè)數(shù)字用“”括起來，表示本循環(huán)內(nèi)不參與數(shù)量調(diào)整，而其他的數(shù)字則減1。重復(fù)上述過程，排出護(hù)士工作的計(jì)劃。 13 護(hù)士需求數(shù)量與排