作業(yè)排序與控制

1、作業(yè)排序與控制1作業(yè)排序與控制作業(yè)排序與控制作業(yè)排序與控制2一、作業(yè)排序問題的概念1、作業(yè)排序與作業(yè)計(jì)劃作業(yè)排序（Sequencing）是指為每臺(tái)設(shè)備、每位員工具體確定每天的工作任務(wù)和工作順序的過程。作業(yè)排序與作業(yè)計(jì)劃（Scheduling）是有區(qū)別的。一般來說，作業(yè)排序只是確定工件在機(jī)器設(shè)備上的加工順序，而作業(yè)計(jì)劃則不僅要確定工件的加工順序，還要確定機(jī)器設(shè)備加工每個(gè)工件的開始時(shí)間和完成時(shí)間。作業(yè)排序與控制3作業(yè)排序問題的概念2、作業(yè)排序的主要目標(biāo)滿足交貨日期的需要。降低在制品庫存，加快流動(dòng)資金周轉(zhuǎn)?？s短提前期。降低機(jī)器設(shè)備的準(zhǔn)備時(shí)間和準(zhǔn)備成本。充分利用機(jī)器設(shè)備和勞動(dòng)力。作業(yè)排序與控制4作業(yè)排

2、序問題的概念3、作業(yè)排序問題的分類根據(jù)行業(yè)的不同，排序問題可分為制造業(yè)的排序問題和服務(wù)業(yè)的排序問題。根據(jù)排序的對(duì)象分，可分為勞動(dòng)力（或服務(wù)者）排序和生產(chǎn)作業(yè)（或服務(wù)對(duì)象）排序。對(duì)于多臺(tái)設(shè)備的排序問題，又可根據(jù)加工路線分為單件作業(yè)（Job shop）排序問題和流水作業(yè)（Flow shop）排序問題。按工件或顧客到達(dá)工作地或服務(wù)臺(tái)的具體情況，可分為靜態(tài)排序問題和動(dòng)態(tài)排序問題。作業(yè)排序與控制5二、制造業(yè)中的n/m排序問題只討論所有工件在各個(gè)工作地的加工順序都相同的情況。為了便于說明，我們將n種工件在m臺(tái)設(shè)備上加工的排序問題表示為n/m。作業(yè)排序與控制61、n/1 排序的優(yōu)先規(guī)則最短加工時(shí)間規(guī)則SPT

3、（shortest processing time）或SOT（shortest operation time）：優(yōu)先選擇加工時(shí)間最短的工件。最早到期規(guī)則EDD（earliest due date）：優(yōu)先選擇完工期限最早的工件。先到先服務(wù)規(guī)則FCFS（first come first served）：優(yōu)先選擇最早進(jìn)入排序集合的工件。最少工作量規(guī)則LWKR（Least work remaining）：優(yōu)先選擇余下加工時(shí)間最短的工件。最多工作量規(guī)則MWKR（most work remaining）：優(yōu)先選擇余下加工時(shí)間最長的工件。最小關(guān)鍵比例規(guī)則SCR（smallest critical ratio

4、）：優(yōu)先選擇關(guān)鍵比例最小的工件，其中，關(guān)鍵比例 =（交貨期 - 當(dāng)前期）/ 余下的加工時(shí)間。作業(yè)排序與控制7n/1 排序在評(píng)價(jià)作業(yè)排序方案時(shí)，工件流程時(shí)間、工件延期交貨天數(shù)、時(shí)間跨度和平均工件庫存數(shù)是幾個(gè)主要的績效評(píng)價(jià)指標(biāo)。作業(yè)排序與控制8n/1排序問題例如，某加工車間要為2003年9月份加工的6批產(chǎn)品進(jìn)行作業(yè)排序，每批的件數(shù)相同，都是1000件，公司對(duì)各種產(chǎn)品的加工時(shí)間都設(shè)定了工時(shí)定額，銷售部門提出了各種產(chǎn)品的預(yù)定交貨期。作業(yè)排序與控制9n/1排序問題 方案1：遵循FCFS規(guī)則排序。FCFS的排序順序是按照待加工的產(chǎn)品從上一道工序轉(zhuǎn)到該加工工序的先后順序來確定的，即如表11-3所示，BY05

5、0GL310GM270BY471 LN002LY120總流程時(shí)間總流程時(shí)間 = 158 天天平均流程時(shí)間平均流程時(shí)間 = 總流程時(shí)間總流程時(shí)間/型號(hào)數(shù)型號(hào)數(shù)=158/6=26.3天天平均延期交貨天數(shù)平均延期交貨天數(shù) = 延期交貨總天數(shù)延期交貨總天數(shù)/型號(hào)數(shù)型號(hào)數(shù)=53/6=8.83天天時(shí)間跨度時(shí)間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 總流程時(shí)間總流程時(shí)間/時(shí)間跨度時(shí)間跨度批量批量=158/401000=3950件件作業(yè)排序與控制10n/1排序問題 方案2：采用SPT規(guī)則。SPT優(yōu)先規(guī)則為優(yōu)先選擇加工時(shí)間最短的產(chǎn)品。根據(jù)SPT規(guī)則，這六批不同的產(chǎn)品在該加工工序的順序?yàn)長N00

6、2LY120BY471GL310GM270BY050總流程時(shí)間總流程時(shí)間 = 120 天天平均流程時(shí)間平均流程時(shí)間 = 120/6=20天天平均延期交貨天數(shù)平均延期交貨天數(shù) = 38/6=6.3天天時(shí)間跨度時(shí)間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 120/401000=3000件件作業(yè)排序與控制11n/1排序問題 方案3：采用EDD規(guī)則。EDD規(guī)則將最早預(yù)定交貨期限作為優(yōu)先選擇標(biāo)準(zhǔn)。根據(jù)EDD規(guī)則，這六批產(chǎn)品的加工順序?yàn)镃AEBDF總流程時(shí)間總流程時(shí)間 = 144 天天平均流程時(shí)間平均流程時(shí)間 = 144/6=24天天平均延期交貨天數(shù)平均延期交貨天數(shù) = 37/6=6.17

7、天天時(shí)間跨度時(shí)間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 144/401000=3600臺(tái)臺(tái)作業(yè)排序與控制12n/1排序問題 方案4：采用SCR規(guī)則。關(guān)鍵比例=（預(yù)期交貨期當(dāng)前日期）/檢驗(yàn)時(shí)間，根據(jù)SCR規(guī)則，這六批產(chǎn)品的加工順序?yàn)镚M270GL310BY050BY471LY120LN002總流程時(shí)間總流程時(shí)間 = 155 天天平均流程時(shí)間平均流程時(shí)間 = 155/6=25.8天天平均延期交貨天數(shù)平均延期交貨天數(shù) = 47/6=7.83天天時(shí)間跨度時(shí)間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 155/401000=3875臺(tái)臺(tái)作業(yè)排序與控制13n/1排序問題 將

8、以上四種規(guī)則的排序結(jié)果匯總，得以下表格從以上例子可知，從以上例子可知，F(xiàn)CFS和和SCR兩種規(guī)則的效率較低，既導(dǎo)致較高的平均流程時(shí)間，有造成兩種規(guī)則的效率較低，既導(dǎo)致較高的平均流程時(shí)間，有造成較多的在制品庫存。一般而言，較多的在制品庫存。一般而言，SPT和和EDD是兩種較優(yōu)的排序規(guī)則，是企業(yè)排序時(shí)常用的是兩種較優(yōu)的排序規(guī)則，是企業(yè)排序時(shí)常用的優(yōu)先規(guī)則。優(yōu)先規(guī)則。SPT規(guī)則可使工件的平均流程時(shí)間最短，從而減少在制品的庫存數(shù)量，從而減少規(guī)則可使工件的平均流程時(shí)間最短，從而減少在制品的庫存數(shù)量，從而減少企業(yè)的資金占用，降低成本。企業(yè)的資金占用，降低成本。EDD規(guī)則可使工件延期交付時(shí)間較小，能夠?qū)е螺^

9、高的客戶規(guī)則可使工件延期交付時(shí)間較小，能夠?qū)е螺^高的客戶滿意水平。滿意水平。作業(yè)排序與控制14n/2排序問題n/2排序問題是指n種工件在2臺(tái)機(jī)器設(shè)備（工作地）上進(jìn)行加工的排序問題。假設(shè)有n個(gè)工件的加工要經(jīng)過兩臺(tái)設(shè)備，并且所有工件的加工路線都相同。在這種情況下，全部完工時(shí)間是一個(gè)關(guān)鍵的評(píng)價(jià)標(biāo)準(zhǔn)，排序的目標(biāo)是使全部完工時(shí)間最短對(duì)n/2的排序問題，Johnson于1954年提出了一個(gè)有效算法作業(yè)排序與控制15n/2排序問題Johnson算法的適用條件排序的目標(biāo)函數(shù)是使全部完工時(shí)間最小工件在兩臺(tái)設(shè)備上的加工順序完全相同所有工作同時(shí)到達(dá)第一臺(tái)設(shè)備等待加工每種工件在每臺(tái)設(shè)備上的加工時(shí)間均已知作業(yè)排序與控制16Johnson算法的步驟 先作n個(gè)工件在兩臺(tái)設(shè)備上的加工時(shí)間的工時(shí)矩陣。在工時(shí)矩陣M中找出最小元素aij，若最小元素不止一個(gè)，可任選其一。如果最短的加工時(shí)間出現(xiàn)在第一臺(tái)設(shè)備上，則對(duì)應(yīng)的工件應(yīng)排在最前位置；如果最短的加工時(shí)間出現(xiàn)在第二臺(tái)設(shè)備上，則對(duì)應(yīng)的工件排在最后位置。從加工時(shí)間矩陣中劃去已排序的工件，然后對(duì)余下的工件重復(fù)步驟（2）和步驟（3），直到全部工件都被安排完。作業(yè)排序