作業(yè)排序與控制

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

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

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

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

5、總流程時間總流程時間 = 158 天天平均流程時間平均流程時間 = 總流程時間總流程時間/型號數(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總流程時

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

7、數(shù) = 144/401000=3600臺臺精選課件12n/1排序問題 方案4：采用SCR規(guī)則。關鍵比例=（預期交貨期當前日期）/檢驗時間，根據(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ī)則的排序結果匯總，得以下表格從以上例子可知，從以上例子可知，F(xiàn)CFS

8、和和SCR兩種規(guī)則的效率較低，既導致較高的平均流程時間，兩種規(guī)則的效率較低，既導致較高的平均流程時間，有造成較多的在制品庫存。一般而言，有造成較多的在制品庫存。一般而言，SPT和和EDD是兩種較優(yōu)的排序規(guī)則，是企業(yè)是兩種較優(yōu)的排序規(guī)則，是企業(yè)排序時常用的優(yōu)先規(guī)則。排序時常用的優(yōu)先規(guī)則。SPT規(guī)則可使工件的平均流程時間最短，從而減少在制品規(guī)則可使工件的平均流程時間最短，從而減少在制品的庫存數(shù)量，從而減少企業(yè)的資金占用，降低成本。的庫存數(shù)量，從而減少企業(yè)的資金占用，降低成本。EDD規(guī)則可使工件延期交付時規(guī)則可使工件延期交付時間較小，能夠?qū)е螺^高的客戶滿意水平。間較小，能夠?qū)е螺^高的客戶滿意水平。精

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