作業(yè)排序與控制

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

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

3、eration time）：優(yōu)先選擇加工時間最短的工件。最早到期規(guī)則EDD（earliest due date）：優(yōu)先選擇完工期限最早的工件。先到先服務(wù)規(guī)則FCFS（first come first served）：優(yōu)先選擇最早進入排序集合的工件。最少工作量規(guī)則LWKR（Least work remaining）：優(yōu)先選擇余下加工時間最短的工件。最多工作量規(guī)則MWKR（most work remaining）：優(yōu)先選擇余下加工時間最長的工件。最小關(guān)鍵比例規(guī)則SCR（smallest critical ratio）：優(yōu)先選擇關(guān)鍵比例最小的工件，其中，關(guān)鍵比例 =（交貨期 - 當前期）/ 余下的加

4、工時間。7n/1 排序在評價作業(yè)排序方案時，工件流程時間、工件延期交貨天數(shù)、時間跨度和平均工件庫存數(shù)是幾個主要的績效評價指標。8n/1排序問題例如，某加工車間要為2003年9月份加工的6批產(chǎn)品進行作業(yè)排序，每批的件數(shù)相同，都是1000件，公司對各種產(chǎn)品的加工時間都設(shè)定了工時定額，銷售部門提出了各種產(chǎn)品的預(yù)定交貨期。9n/1排序問題 方案1：遵循FCFS規(guī)則排序。FCFS的排序順序是按照待加工的產(chǎn)品從上一道工序轉(zhuǎn)到該加工工序的先后順序來確定的，即如表11-3所示，BY050GL310GM270BY471 LN002LY120總流程時間總流程時間 = 158 天天平均流程時間平均流程時間 = 總流

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

6、平均延期交貨天數(shù)平均延期交貨天數(shù) = 38/6=6.3天天時間跨度時間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 120/401000=3000件件11n/1排序問題 方案3：采用EDD規(guī)則。EDD規(guī)則將最早預(yù)定交貨期限作為優(yōu)先選擇標準。根據(jù)EDD規(guī)則，這六批產(chǎn)品的加工順序為CAEBDF總流程時間總流程時間 = 144 天天平均流程時間平均流程時間 = 144/6=24天天平均延期交貨天數(shù)平均延期交貨天數(shù) = 37/6=6.17天天時間跨度時間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 144/401000=3600臺臺12n/1排序問題 方案4：采用SCR規(guī)則。關(guān)

7、鍵比例=（預(yù)期交貨期當前日期）/檢驗時間，根據(jù)SCR規(guī)則，這六批產(chǎn)品的加工順序為GM270GL310BY050BY471LY120LN002總流程時間總流程時間 = 155 天天平均流程時間平均流程時間 = 155/6=25.8天天平均延期交貨天數(shù)平均延期交貨天數(shù) = 47/6=7.83天天時間跨度時間跨度 = 40 天天平均在制品庫存數(shù)平均在制品庫存數(shù) = 155/401000=3875臺臺13n/1排序問題 將以上四種規(guī)則的排序結(jié)果匯總，得以下表格從以上例子可知，從以上例子可知，F(xiàn)CFS和和SCR兩種規(guī)則的效率較低，既導(dǎo)致較高的平均流程時間，有造成兩種規(guī)則的效率較低，既導(dǎo)致較高的平均流程時

8、間，有造成較多的在制品庫存。一般而言，較多的在制品庫存。一般而言，SPT和和EDD是兩種較優(yōu)的排序規(guī)則，是企業(yè)排序時常用的是兩種較優(yōu)的排序規(guī)則，是企業(yè)排序時常用的優(yōu)先規(guī)則。優(yōu)先規(guī)則。SPT規(guī)則可使工件的平均流程時間最短，從而減少在制品的庫存數(shù)量，從而減少規(guī)則可使工件的平均流程時間最短，從而減少在制品的庫存數(shù)量，從而減少企業(yè)的資金占用，降低成本。企業(yè)的資金占用，降低成本。EDD規(guī)則可使工件延期交付時間較小，能夠?qū)е螺^高的客戶規(guī)則可使工件延期交付時間較小，能夠?qū)е螺^高的客戶滿意水平。滿意水平。14n/2排序問題n/2排序問題是指n種工件在2臺機器設(shè)備（工作地）上進行加工的排序問題。假設(shè)有n個工件的

9、加工要經(jīng)過兩臺設(shè)備，并且所有工件的加工路線都相同。在這種情況下，全部完工時間是一個關(guān)鍵的評價標準，排序的目標是使全部完工時間最短對n/2的排序問題，Johnson于1954年提出了一個有效算法15n/2排序問題Johnson算法的適用條件排序的目標函數(shù)是使全部完工時間最小工件在兩臺設(shè)備上的加工順序完全相同所有工作同時到達第一臺設(shè)備等待加工每種工件在每臺設(shè)備上的加工時間均已知16Johnson算法的步驟 先作n個工件在兩臺設(shè)備上的加工時間的工時矩陣。在工時矩陣M中找出最小元素aij，若最小元素不止一個，可任選其一。如果最短的加工時間出現(xiàn)在第一臺設(shè)備上，則對應(yīng)的工件應(yīng)排在最前位置；如果最短的加工時間出現(xiàn)在第二臺設(shè)備上，則對應(yīng)