作業(yè)排序(生產管理(華中科技大學崔南方).ppt
《作業(yè)排序(生產管理(華中科技大學崔南方).ppt》由會員分享，可在線閱讀，更多相關《作業(yè)排序(生產管理(華中科技大學崔南方).ppt（38頁珍藏版）》請在裝配圖網上搜索。
第六章作業(yè)排序,一、基本概念二、最長流程時間三、n/2/F/Fmax問題的算法四、一般n/m/P/Fmax問題的啟發(fā)式算法五、單件車間排序問題,一、基本概念,1、排序排序就是要將不同的工作任務安排一個執(zhí)行的順序，使預定的目標最優(yōu)化。實際上就是要解決如何按時間的先后，將有限的人力、物力資源分配給不同工作任務，使預定目標最優(yōu)化的問題。,一、基本概念,排序中常用的幾個概念工件（Job）：服務對象；機器（Machine、Processor）：服務者。,如：n個零件在機器上加工，則零件是工件，設備是機器；工人維修設備，出故障的設備是工件，工人是機器。,一、基本概念,所以，作業(yè)排序也就是要確定工件在機器上的加工順序，可用一組工件代號的一種排列來表示。如可用（1，6，5，4，3，2）表示加工順序：J1—J6—J5—J4—J3—J2。,一、基本概念,2、作業(yè)計劃（Scheduling）作業(yè)計劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機器加工每個工件的開工時間和完工時間。如果按最早可能開（完）工時間來編排作業(yè)計劃，則排序完后，作業(yè)計劃也就確定了。,一、基本概念,3、排序問題的分類與表示1）單臺機器與多臺機器的排序問題。2）流水車間與單件車間排序問題。,一、基本概念,流水車間排序問題的基本特征：每個工件的加工路線都一樣。如車—銑—磨。這里指的是工件的加工流向一致，并不要求每個工件必須在每臺機器上加工。如有的工件為車—磨，有的為銑—磨。不僅加工路線一致，而且所有工件在各臺機器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序為：J1—J3—J2，則表示所有機器都是先加工J1，然后加工J3，最后加工J2。,一、基本概念,單件車間排序問題的基本特征：每個工件都有其獨特的加工路線，工件沒有一定的流向。,一、基本概念,3）表示方法一般正規(guī)的表示方法為：n/m/A/Bn：工件數(shù)；m：機器數(shù)；A：車間類型（F、P、G）；B：目標函數(shù),一、基本概念,4）一般來說，排列排序問題的最優(yōu)解不一定是相應流水車間排序問題的最優(yōu)解，但一般是比較好的解。而對于僅有2臺或3臺機器的情況，則排列排序問題的最優(yōu)解一定是相應流水車間排序問題的最優(yōu)解。,一、基本概念,4、排序問題的假設條件一個工件不能同時在幾臺不同的機器上加工。工件在加工過程中采取平行移動方式。不允許中斷。每道工序只在一臺機器上完成。每臺機器同時只能加工一個工件。工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關。,二、最長流程時間,最長流程時間（加工周期）：從第一個工件在第一臺機器上加工起到最后一個工件在最后一臺機器上加工完畢為止所經過的時間。假定所有工件的到達時間都為0，則Fmax等于排在末位加工的工件在車間的停留時間。,二、最長流程時間,計算Fmax的幾個假定條件：機器M1不會發(fā)生空閑；對其它機器，能對某一工件加工必須具備2個條件：機器必須完成排前一位的工件的加工；要加工的工件的上道工序已經完工。,二、最長流程時間,二、最長流程時間,,,,,,,,i,pi1,pi2,pi3,pi4,6,1,5,2,4,3,2,5,5,1,4,4,5,4,4,4,5,3,2,5,8,2,1,7,5,3,3,6,7,4,2,6,10,12,13,16,7,11,15,20,27,33,12,17,22,30,35,42,13,21,25,32,38,46,三、n/2/F/Fmax問題的算法,Johnson算法：假定：ai為工件Ji在機器M1上的加工時間，bi為工件Ji在機器M2上的加工時間，每個工件按M1—M2的路線加工。,三、n/2/F/Fmax問題的算法,Johnson算法的步驟：從加工時間矩陣中找出最短的加工時間。若最短時間出現(xiàn)在M1上，則對應的工件盡可能往前排。若最短時間出現(xiàn)在M2上，則對應的工件盡可能往后排。若最短時間有多個，則任選一個。劃去已排序的工件。若所有工件都已排序，則停止，否則重復上述步驟。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,對于一般的n/m/P/Fmax問題，可以用分支定界法求得最優(yōu)解，但計算量很大。實際中，可以用啟發(fā)式算法求近優(yōu)解。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,1、Palmer法計算工件斜度指標?i：m:機器數(shù)pik：工件i在機器k上的加工時間。i=1,2,?,n排序方法:按?i從大到小的順序排列。按排序的順序計算Fmax,四、一般n/m/P/Fmax問題的啟發(fā)式算法,2、關鍵工件法：計算Pi=?Pij，找出Pi最長的工件，將之作為關鍵工件C。對其余工件，若Pi1≤Pim，則按Pi1由小到大排成序列SA。若Pi1>Pim，則按Pim由大到小排成序列SB。順序（SA，C，SB）即為近優(yōu)解。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,得到的加工順序為(1，2，3，4),四、一般n/m/P/Fmax問題的啟發(fā)式算法,3、CDS法：CDS法是Johnson算法的擴展方法，從M-1個排序中找出近優(yōu)解。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,L＝1，按Johnson算法得到加工順序(1，2，3，4)，F(xiàn)max＝28L＝2，按Johnson算法得到加工順序(2，3，1，4)，F(xiàn)max＝29取順序(1，2，3，4）為最優(yōu)順序。,五、單件車間排序問題（n/m/G/Fmax）,1、問題描述(i，j，k)：表示工件i的第j道工序是在機器k上進行。加工描述矩陣D：每一行描述一個工件的加工，每一列的工序序號相同。,五、單件車間排序問題（n/m/G/Fmax）,加工時間矩陣T：與D相對應。,,五、單件車間排序問題（n/m/G/Fmax）,加工順序矩陣S：每一行與機器相對應，每一列與工件相對應。,,S=,1,1,12,2,1,1,3,22,3,2,,,2,1,31,2,3,五、單件車間排序問題（n/m/G/Fmax）,用方塊圖表示：,,,五、單件車間排序問題（n/m/G/Fmax）,2、能動作業(yè)計劃的構成各工序都按最早可能開(完)工時間安排且任何一臺機器的每段空閑時間都不足以加工一道可加工工序。符號說明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序構成的部分作業(yè)計劃Tk{Ot}中工序Ok的最早可能開工時間T’k{Ot}中工序Ok的最早可能完工時間,五、單件車間排序問題（n/m/G/Fmax）,能動作業(yè)計劃的構成步驟：①設t＝1，{St}為空，{Ot}為各工件第一道工序的集合。②求最小的最早完工時間T*=min{T’k},并找到出現(xiàn)T*的機器M*，若有多臺，任選一臺。③從{Ot}中跳出滿足以下兩條件的工序Oj需要機器M*加工；Tj
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞：
- 作業(yè) 排序 生產管理 華中科技大學 南方
裝配圖網所有資源均是用戶自行上傳分享，僅供網友學習交流，未經上傳用戶書面授權，請勿作他用。
鏈接地址：http://m.jqnhouse.com/p-11519806.html