第十一章 作業(yè)排序

1、第十一章第十一章 作業(yè)排序作業(yè)排序 第一節(jié)第一節(jié) 作業(yè)排序的基本概念作業(yè)排序的基本概念 一、作業(yè)計(jì)劃與排序（一、作業(yè)計(jì)劃與排序（scheduling and sequencing） w 工件等待 w 機(jī)器空閑 二、作業(yè)排序問題的分類二、作業(yè)排序問題的分類 w 勞動(dòng)力作業(yè)排序（服務(wù)業(yè)）勞動(dòng)力作業(yè)排序（服務(wù)業(yè)） w 生產(chǎn)作業(yè)排序（制造業(yè)）生產(chǎn)作業(yè)排序（制造業(yè)） 單件車間（job-shop） n按機(jī)器的種類和數(shù)量分 流水車間 (flow-shop) 靜態(tài)排序 n按工件到達(dá)車間情況分 動(dòng)態(tài)排序 單目標(biāo)（平均流程時(shí)間最短） n按目標(biāo)函數(shù)的性質(zhì)分 多目標(biāo) (誤期完工工件數(shù)最少) 三、作業(yè)排序的任務(wù)和目標(biāo)三

2、、作業(yè)排序的任務(wù)和目標(biāo) 有效的作業(yè)排序系統(tǒng)應(yīng)能做到： （1） 對(duì)將要做的工作進(jìn)行優(yōu)先權(quán)設(shè)定； （2）以可利用和所需的能力為基礎(chǔ)，針對(duì)具體設(shè)備分配任務(wù)及 人力； （3） 以實(shí)施為目標(biāo)分配工作，使工作任務(wù)如期完成； （4） 不斷（周期性）監(jiān)督以確保任務(wù)的完成； （5） 辨識(shí)實(shí)施中的問題或異常情況，運(yùn)用其它方法解決問題； （6） 根據(jù)現(xiàn)狀或訂單的變化對(duì)目前的作業(yè)排序進(jìn)行回顧和修改。 第二節(jié)第二節(jié) 制造業(yè)中的生產(chǎn)作業(yè)排序制造業(yè)中的生產(chǎn)作業(yè)排序 一、甘特圖一、甘特圖 w 作業(yè)進(jìn)度圖 w 機(jī)器圖 圖圖11-1 作業(yè)進(jìn)度甘特圖作業(yè)進(jìn)度甘特圖 工作 4/17 4/18 4/19 4/20 4/21 4/22

3、4/23 4/24 4/25 4/26 A B C 圖圖11-2 機(jī)器甘特圖機(jī)器甘特圖 機(jī)器 4/22 4/23 4/24 4/25 4/26 4/27 4/28 4/29 磨床 拋光機(jī) A B A C B C 圖例： 開始工作 結(jié)束工作 計(jì)劃時(shí)間 實(shí)際進(jìn)度 非生產(chǎn)時(shí)間 二、作業(yè)排序方案的評(píng)價(jià)標(biāo)準(zhǔn)二、作業(yè)排序方案的評(píng)價(jià)標(biāo)準(zhǔn) （1）工件流程時(shí)間 n工作可以開始加工至完工的時(shí)間，包括工件在各機(jī)器之間的移動(dòng)時(shí)間、等待時(shí)間、加 工時(shí)間以及由于機(jī)器故障、部件無(wú)法得到等問題引起的延遲時(shí)間等。 （2）全部完工時(shí)間 n 完成一組工作所需的全部時(shí)間。 （3）延遲 n可以用比預(yù)定完工時(shí)間延遲了的時(shí)間部分來(lái)表示；可

4、也可以用來(lái)按預(yù)定時(shí)間完工的工 件數(shù)占總工件數(shù)的百分比表示。 （4）在制品庫(kù)存（WIP） n可以用工件個(gè)數(shù)、貨幣價(jià)值或可供應(yīng)的周數(shù)表示。 （5）總庫(kù)存 n計(jì)劃入庫(kù)量和現(xiàn)有庫(kù)存量的總和。 （6）利用率 n一臺(tái)機(jī)器或一個(gè)工人的有效時(shí)間占總工作時(shí)間的百分比。 上述標(biāo)準(zhǔn)可以用具有平均和偏差的統(tǒng)計(jì)分布來(lái)表示，且它們之間并不完全獨(dú)立。 三、優(yōu)先調(diào)度規(guī)則三、優(yōu)先調(diào)度規(guī)則 利用優(yōu)先調(diào)度（排序）規(guī)則，在同一工作地等待加工的工作中決定下一項(xiàng) 應(yīng)該進(jìn)行加工的工作。而所謂調(diào)度方法，就是運(yùn)用若干預(yù)先規(guī)定的優(yōu)先順序規(guī) 則，順次決定下一個(gè)應(yīng)被加工的工件的排序方法。 （1） FCFS(First Come First Serv

5、e)規(guī)則； （2） SPT (Shortest Processing Time) 規(guī)則； （3） EDD(Earliest Due Date ) 規(guī)則； （4） SCR (Smallest Critical Ration) 規(guī)則； n臨界比=到交貨期為止的剩余時(shí)間/剩余加工時(shí)間（擁有/需要） （5） MWKR(Most Work Remaining)； n 優(yōu)先選擇剩余加工時(shí)間最長(zhǎng)工件加工。 （6） LMKR(Least Work Remaining)規(guī)則； n 優(yōu)先選擇剩余加工時(shí)間最短工件加工。 （7） MOOPNR(Most Operations Remaining)規(guī)則； n優(yōu)先選擇剩余

6、工序數(shù)最多工件加工。 （8）RANDOM規(guī)則。 n隨機(jī)挑選下一個(gè)工件。 w SPT可使工件的平均流程時(shí)間最短，從而減少在制品數(shù)量； w FCFS來(lái)自排隊(duì)論，對(duì)工件比較公平； wEDD和SCR可使工件延誤時(shí)間最??； wMWKR使不同工作量的工件完工時(shí)間盡量接近； wLWKR使工作量小的工件盡快完成。 SPT+MWKR+RANDOM 排序要求信息：加工要求（工藝）和實(shí)際完成情況： 加工要求信息：計(jì)劃完工期（交貨期）、工藝路線、標(biāo)準(zhǔn)作業(yè)交換時(shí)間（準(zhǔn) 終）、加工時(shí)間（單件）、各工序預(yù)計(jì)等待時(shí)間（如需要）、各工序可替代 設(shè)備以及所需的原材料和零件等。 實(shí)際完成情況：工件目前位置（在某道工序上加工、或等待

7、加工）、已完成 工序、在每一工序的實(shí)際到達(dá)和離開時(shí)間、實(shí)際加工時(shí)間和作業(yè)交換時(shí)間、 各工序所產(chǎn)業(yè)的廢品等。 四、局部與整體優(yōu)先規(guī)則四、局部與整體優(yōu)先規(guī)則 w優(yōu)先規(guī)則為局部?jī)?yōu)先規(guī)則（排序時(shí)僅以單個(gè)工作地隊(duì) 列的信息為依據(jù)）：EDD、FCFS、SPT，和整體規(guī) 則（不僅根據(jù)工件正在排序的工序的工藝參數(shù)，而且 還要考慮其他工序）：SCR、MWKR、LWKR 和 MOPNR。 （一）局部?jī)?yōu)先規(guī)則（一）局部?jī)?yōu)先規(guī)則 表11-1 發(fā)動(dòng)機(jī)機(jī)殼的加工與取貨信息 發(fā)動(dòng)機(jī)機(jī)殼 機(jī)殼1 機(jī)殼2機(jī)殼3機(jī)殼4機(jī)殼5 標(biāo)準(zhǔn)加工時(shí)間（h）8615312 預(yù)計(jì)取貨時(shí)間（h）1012201822 表表11-2 SPT規(guī)則排序結(jié)

8、果規(guī)則排序結(jié)果 機(jī)殼加 工次序 開 始 時(shí)間 加 工 時(shí)間 結(jié)束 時(shí)間 流程 時(shí)間 預(yù) 計(jì) 取 貨時(shí)間 實(shí)際取 貨時(shí)間 提前拖延 機(jī)殼40333181815 機(jī)殼2369912123 機(jī)殼198171710177 機(jī)殼51712292922297 機(jī)殼329154444204424 總數(shù)441021201838 平均數(shù)20.43.67.6 平均在制品庫(kù)存=102/44=2.32個(gè) 平均總庫(kù)存=120/44=2.73個(gè) 平均在制品庫(kù)存=各工件流程時(shí)間之和/全部加工時(shí)間 平均總庫(kù)存=各工件實(shí)際取貨時(shí)間之和/全部加工時(shí)間 總庫(kù)存=在制品+已完成、正等待顧客取走的完成品 表表11-3 EDD規(guī)則排序結(jié)

9、果規(guī)則排序結(jié)果 機(jī)殼加 工次序 開 始 時(shí)間 加 工 時(shí)間 結(jié)束時(shí) 間 流程 時(shí)間 預(yù) 計(jì) 取 貨時(shí)間 實(shí)際取 貨時(shí)間 提前拖延 機(jī)殼1088810102 機(jī)殼286141412122 機(jī)殼4143171718181 機(jī)殼317153232203212 機(jī)殼532124444224422 總數(shù)44115118336 平均數(shù)23.00.67.2 平均在制品庫(kù)存=115/44=2.61個(gè) 平均總庫(kù)存=118/44=2.68個(gè) 比較表11-2和表11-3可以看出，用SPT規(guī)則排序，其平 均流程更短，平均在制品庫(kù)存更少；而用EDD規(guī)則排序， 可給顧客提供更好的服務(wù)：平均延遲和總延遲均較少， 也提供了更

10、低的總庫(kù)存水平。 局部?jī)?yōu)先規(guī)則可用于多工作地排序問題。 （二）整體優(yōu)先規(guī)則（二）整體優(yōu)先規(guī)則 w運(yùn)用前述整體優(yōu)先規(guī)則排序。 w兩臺(tái)機(jī)器的流水車間作業(yè)排序問題：待加工工件的工藝路線相同。 w使在流水車間中兩臺(tái)機(jī)器上加工一組工件的完工時(shí)間最小使第二臺(tái)機(jī)器的空 閑時(shí)間最小。 wSMJohnson（1954年）提出的算法： （1）設(shè) 為工件i（i=1， ，n）在機(jī)器j(j=1,2)上的加工時(shí)間。在矩陣中找出最小的 值， 如果有兩個(gè)以上相同的最小值，則任選一個(gè)。 （2）若最小 出現(xiàn)在機(jī)器1上（j=1），則對(duì)應(yīng)工件盡量往前排；若最短加工時(shí)間出現(xiàn)在機(jī) 器2上，則對(duì)應(yīng)的工件盡可能往后排。 （3）從加工矩陣（

11、）中劃去已排序的工件，然后重復(fù)步驟（1）和（2），直至全部工件 被安排。 w一般求解采用啟發(fā)式算法。 ij a ij a ij a ij a 應(yīng)用事例應(yīng)用事例11-1 五臺(tái)儀器修復(fù)作業(yè)排序。五臺(tái)儀器修復(fù)作業(yè)排序。 表11-4 修理時(shí)間（h） 儀器 Y1Y2Y3 Y4Y5 工序1 12451510 工序2 2253168 表11-5 排序結(jié)果 步驟 排序 1 2 3 4 5 Y3 Y2 Y3 Y2 Y5 Y3 Y2 Y1 Y5 Y3 Y2 Y1 Y4 Y5 Y3 五、作業(yè)排序中的兩種不同約束環(huán)境五、作業(yè)排序中的兩種不同約束環(huán)境 w 設(shè)備數(shù)有限、人員無(wú)限（以上情況）； w 人員數(shù)有限、設(shè)備數(shù)無(wú)限，

12、或人員數(shù)小于設(shè)備數(shù)?？?采用與前類似的調(diào)度規(guī)則來(lái)作出人員安排決策。 第三節(jié)第三節(jié) 服務(wù)業(yè)中的服務(wù)作業(yè)排序服務(wù)業(yè)中的服務(wù)作業(yè)排序 一、服務(wù)作業(yè)排序與生產(chǎn)作業(yè)排序的主要區(qū)別一、服務(wù)作業(yè)排序與生產(chǎn)作業(yè)排序的主要區(qū)別 （1）所提供產(chǎn)品的類型 服務(wù)生產(chǎn)中，有顧客的參與，作業(yè)排序?qū)λ麄冇兄苯佑绊懀?因而成為服務(wù)的一部人；在制造業(yè)中，生產(chǎn)作業(yè)排序地最終產(chǎn)品使用者無(wú)直接 影響。 （2）排序內(nèi)容 服務(wù)業(yè)中，作業(yè)排序要定義服務(wù)交易的時(shí)間或消耗點(diǎn)；制造業(yè)中，僅 定義產(chǎn)品生產(chǎn)的操作步驟。 （3）過(guò)程控制 服務(wù)業(yè)中，用戶參與服務(wù)過(guò)程，并對(duì)全部操作時(shí)間施加影響；制造業(yè) 中用戶僅與最終產(chǎn)品或交貨時(shí)間相關(guān)。 （4）人員規(guī)模 在顧客化服務(wù)業(yè)中，服務(wù)的輸出與勞動(dòng)的最佳規(guī)模之間的關(guān)系很難確 定；制造業(yè)中，兩者有緊密聯(lián)系，最優(yōu)的作業(yè)排序可以算出。 顧客化服務(wù)：“先到先服務(wù)”、“預(yù)約式”、顧客出參與決策過(guò)程， 通常作為驅(qū)動(dòng)者。 服務(wù)業(yè)服務(wù) 標(biāo)準(zhǔn)化服務(wù)（交通運(yùn)輸、零售業(yè)），更多與設(shè)備、工具相連。 服務(wù)業(yè)中其作業(yè)組織和排序更困難，對(duì)其績(jī)效果影響也更大。 w兩種基本方法： （1） 將服務(wù)需求分配到服務(wù)能力的不同時(shí)間段內(nèi)； （2） 將服務(wù)人員安排到顧客需求