作業(yè)排序與控制排序

作業(yè)排序與控制1精品PPT|實(shí)用可編輯第一頁，共十九頁。一、作業(yè)排序問題的概念1、作業(yè)排序與作業(yè)計(jì)劃作業(yè)排序（Sequencing）是指為每臺設(shè)備、每位員工具體確定每天的工作任務(wù)和工作順序的過程。作業(yè)排序與作業(yè)計(jì)劃（Scheduling）是有區(qū)別的。一般來說，作業(yè)排序只是確定工件在機(jī)器設(shè)備上的加工順序，而作業(yè)計(jì)劃則不僅要確定工件的加工順序，還要確定機(jī)器設(shè)備加工每個工件的開始時間和完成時間。2精品PPT|實(shí)用可編輯第二頁，共十九頁。作業(yè)排序問題的概念2、作業(yè)排序的主要目標(biāo)滿足交貨日期的需要。降低在制品庫存，加快流動資金周轉(zhuǎn)?？s短提前期。降低機(jī)器設(shè)備的準(zhǔn)備時間和準(zhǔn)備成本。充分利用機(jī)器設(shè)備和勞動力。3精品PPT|實(shí)用可編輯第三頁，共十九頁。作業(yè)排序問題的概念3、作業(yè)排序問題的分類根據(jù)行業(yè)的不同，排序問題可分為制造業(yè)的排序問題和服務(wù)業(yè)的排序問題。根據(jù)排序的對象分，可分為勞動力（或服務(wù)者）排序和生產(chǎn)作業(yè)（或服務(wù)對象）排序。對于多臺設(shè)備的排序問題，又可根據(jù)加工路線分為單件作業(yè)（Jobshop）排序問題和流水作業(yè)（Flowshop）排序問題。按工件或顧客到達(dá)工作地或服務(wù)臺的具體情況，可分為靜態(tài)排序問題和動態(tài)排序問題。4精品PPT|實(shí)用可編輯第四頁，共十九頁。二、制造業(yè)中的n/m排序問題只討論所有工件在各個工作地的加工順序都相同的情況。為了便于說明，我們將n種工件在m臺設(shè)備上加工的排序問題表示為n/m。5精品PPT|實(shí)用可編輯第五頁，共十九頁。1、n/1排序的優(yōu)先規(guī)則最短加工時間規(guī)則——SPT（shortestprocessingtime）或SOT（shortestoperationtime）：優(yōu)先選擇加工時間最短的工件。最早到期規(guī)則——EDD（earliestduedate）：優(yōu)先選擇完工期限最早的工件。先到先服務(wù)規(guī)則——FCFS（firstcomefirstserved）：優(yōu)先選擇最早進(jìn)入排序集合的工件。最少工作量規(guī)則——LWKR（Leastworkremaining）：優(yōu)先選擇余下加工時間最短的工件。最多工作量規(guī)則——MWKR（mostworkremaining）：優(yōu)先選擇余下加工時間最長的工件。最小關(guān)鍵比例規(guī)則——SCR（smallestcriticalratio）：優(yōu)先選擇關(guān)鍵比例最小的工件，其中，關(guān)鍵比例=（交貨期-當(dāng)前期）/余下的加工時間。6精品PPT|實(shí)用可編輯第六頁，共十九頁。n/1排序在評價作業(yè)排序方案時，工件流程時間、工件延期交貨天數(shù)、時間跨度和平均工件庫存數(shù)是幾個主要的績效評價指標(biāo)。7精品PPT|實(shí)用可編輯第七頁，共十九頁。n/1排序問題例如，某加工車間要為2003年9月份加工的6批產(chǎn)品進(jìn)行作業(yè)排序，每批的件數(shù)相同，都是1000件，公司對各種產(chǎn)品的加工時間都設(shè)定了工時定額，銷售部門提出了各種產(chǎn)品的預(yù)定交貨期。8精品PPT|實(shí)用可編輯第八頁，共十九頁。n/1排序問題方案1：遵循FCFS規(guī)則排序。FCFS的排序順序是按照待加工的產(chǎn)品從上一道工序轉(zhuǎn)到該加工工序的先后順序來確定的，即如表11-3所示，BY050→GL310→GM270→BY471→LN002→LY120總流程時間=158天平均流程時間=總流程時間/型號數(shù)=158/6=26.3天平均延期交貨天數(shù)=延期交貨總天數(shù)/型號數(shù)=53/6=8.83天時間跨度=40天平均在制品庫存數(shù)=總流程時間/時間跨度×批量=158/40×1000=3950件9精品PPT|實(shí)用可編輯第九頁，共十九頁。n/1排序問題方案2：采用SPT規(guī)則。SPT優(yōu)先規(guī)則為優(yōu)先選擇加工時間最短的產(chǎn)品。根據(jù)SPT規(guī)則，這六批不同的產(chǎn)品在該加工工序的順序?yàn)長N002→LY120→BY471→GL310→GM270→BY050總流程時間=120天平均流程時間=120/6=20天平均延期交貨天數(shù)=38/6=6.3天時間跨度=40天平均在制品庫存數(shù)=120/40×1000=3000件10精品PPT|實(shí)用可編輯第十頁，共十九頁。n/1排序問題方案3：采用EDD規(guī)則。EDD規(guī)則將最早預(yù)定交貨期限作為優(yōu)先選擇標(biāo)準(zhǔn)。根據(jù)EDD規(guī)則，這六批產(chǎn)品的加工順序?yàn)镃→A→E→B→D→F總流程時間=144天平均流程時間=144/6=24天平均延期交貨天數(shù)=37/6=6.17天時間跨度=40天平均在制品庫存數(shù)=144/40×1000=3600臺11精品PPT|實(shí)用可編輯第十一頁，共十九頁。精品PPT·收集整理第十二頁，共十九頁。n/1排序問題方案4：采用SCR規(guī)則。關(guān)鍵比例=（預(yù)期交貨期—當(dāng)前日期）/檢驗(yàn)時間，根據(jù)SCR規(guī)則，這六批產(chǎn)品的加工順序?yàn)镚M270→GL310→BY050→BY471→LY120→LN002總流程時間=155天平均流程時間=155/6=25.8天平均延期交貨天數(shù)=47/6=7.83天時間跨度=40天平均在制品庫存數(shù)=155/40×1000=3875臺13精品PPT|實(shí)用可編輯第十三頁，共十九頁。PPT內(nèi)容概述作業(yè)排序與控制。精品PPT|實(shí)用可編輯。精品PPT|實(shí)用可編輯。1、作業(yè)排序與作業(yè)計(jì)劃。作業(yè)排序（Sequencing）是指為每臺設(shè)備、每位員工具體確定每天的工作任務(wù)和工作順序的過程。作業(yè)排序與作業(yè)計(jì)劃（Scheduling）是有區(qū)別的。只討論所有工件在各個工作地的加工順序都相同的情況。為了便于說明，我們將n種工件在m臺設(shè)備上加工的排序問題表示為n/m。1、n/1排序的優(yōu)先規(guī)則。最早到期規(guī)則——EDD（earliestduedate）：優(yōu)先選擇完工期限最早的工件。最少工作量規(guī)則——LWKR（Leastworkremaining）：優(yōu)先選擇余下加工時間最短的工件。最多工作量規(guī)則——MWKR（mostworkremaining）：優(yōu)先選擇余下加工時間最長的工件。在評價作業(yè)排序方案時，工件流程時間、工件延期交貨天數(shù)、時間跨度和平均工件庫存數(shù)是幾個主要的績效評價指標(biāo)。18第十四頁，共十九頁。n/1排序問題將以上四種規(guī)則的排序結(jié)果匯總，得以下表格從以上例子可知，F(xiàn)CFS和SCR兩種規(guī)則的效率較低，既導(dǎo)致較高的平均流程時間，有造成較多的在制品庫存。一般而言，SPT和EDD是兩種較優(yōu)的排序規(guī)則，是企業(yè)排序時常用的優(yōu)先規(guī)則。SPT規(guī)則可使工件的平均流程時間最短，從而減少在制品的庫存數(shù)量，從而減少企業(yè)的資金占用，降低成本。EDD規(guī)則可使工件延期交付時間較小，能夠?qū)е螺^高的客戶滿意水平。15精品PPT|實(shí)用可編輯第十五頁，共十九頁。n/2排序問題n/2排序問題是指n種工件在2臺機(jī)器設(shè)備（工作地）上進(jìn)行加工的排序問題。假設(shè)有n個工件的加工要經(jīng)過兩臺設(shè)備，并且所有工件的加工路線都相同。在這種情況下，全部完工時間是一個關(guān)鍵的評價標(biāo)準(zhǔn)，排序的目標(biāo)是使全部完工時間最短對n/2的排序問題，Johnson于1954年提出了一個有效算法16精品PPT|實(shí)用可編輯第十六頁，共十九頁。n/2排序問題Johnson算法的適用條件排序的目標(biāo)函數(shù)是使全部完工時間最小工件在兩臺設(shè)備上的加工順序完全相同所有工作同時到達(dá)第一臺設(shè)備等待加工每種工件在每臺設(shè)備上的加工時間均已知17精品PPT|實(shí)用可編輯第十七頁，共十九頁。Johnson算法的步驟

先作n個工件在兩臺設(shè)備上的加工時間的工時矩陣。在工時矩陣M中找出最小元素aij，若最小元素不止一個，可任選其一。如果最短的加工時間出現(xiàn)在第一臺設(shè)備上，則對應(yīng)的工件應(yīng)排在最前位置；如果最短的加工時間出現(xiàn)在第二臺設(shè)備上，則對應(yīng)的工件排在最后位置。從加工時間矩陣中劃去已