作業(yè)排序(生產(chǎn)管理(華中科技大學(xué)崔南方).ppt
《作業(yè)排序(生產(chǎn)管理(華中科技大學(xué)崔南方).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《作業(yè)排序(生產(chǎn)管理(華中科技大學(xué)崔南方).ppt（38頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第六章作業(yè)排序,一、基本概念二、最長(zhǎng)流程時(shí)間三、n/2/F/Fmax問題的算法四、一般n/m/P/Fmax問題的啟發(fā)式算法五、單件車間排序問題,一、基本概念,1、排序排序就是要將不同的工作任務(wù)安排一個(gè)執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。實(shí)際上就是要解決如何按時(shí)間的先后，將有限的人力、物力資源分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問題。,一、基本概念,排序中常用的幾個(gè)概念工件（Job）：服務(wù)對(duì)象；機(jī)器（Machine、Processor）：服務(wù)者。,如：n個(gè)零件在機(jī)器上加工，則零件是工件，設(shè)備是機(jī)器；工人維修設(shè)備，出故障的設(shè)備是工件，工人是機(jī)器。,一、基本概念,所以，作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號(hào)的一種排列來表示。如可用（1，6，5，4，3，2）表示加工順序：J1—J6—J5—J4—J3—J2。,一、基本概念,2、作業(yè)計(jì)劃（Scheduling）作業(yè)計(jì)劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺(tái)機(jī)器加工每個(gè)工件的開工時(shí)間和完工時(shí)間。如果按最早可能開（完）工時(shí)間來編排作業(yè)計(jì)劃，則排序完后，作業(yè)計(jì)劃也就確定了。,一、基本概念,3、排序問題的分類與表示1）單臺(tái)機(jī)器與多臺(tái)機(jī)器的排序問題。2）流水車間與單件車間排序問題。,一、基本概念,流水車間排序問題的基本特征：每個(gè)工件的加工路線都一樣。如車—銑—磨。這里指的是工件的加工流向一致，并不要求每個(gè)工件必須在每臺(tái)機(jī)器上加工。如有的工件為車—磨，有的為銑—磨。不僅加工路線一致，而且所有工件在各臺(tái)機(jī)器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序?yàn)椋篔1—J3—J2，則表示所有機(jī)器都是先加工J1，然后加工J3，最后加工J2。,一、基本概念,單件車間排序問題的基本特征：每個(gè)工件都有其獨(dú)特的加工路線，工件沒有一定的流向。,一、基本概念,3）表示方法一般正規(guī)的表示方法為：n/m/A/Bn：工件數(shù)；m：機(jī)器數(shù)；A：車間類型（F、P、G）；B：目標(biāo)函數(shù),一、基本概念,4）一般來說，排列排序問題的最優(yōu)解不一定是相應(yīng)流水車間排序問題的最優(yōu)解，但一般是比較好的解。而對(duì)于僅有2臺(tái)或3臺(tái)機(jī)器的情況，則排列排序問題的最優(yōu)解一定是相應(yīng)流水車間排序問題的最優(yōu)解。,一、基本概念,4、排序問題的假設(shè)條件一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。工件在加工過程中采取平行移動(dòng)方式。不允許中斷。每道工序只在一臺(tái)機(jī)器上完成。每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無關(guān)。,二、最長(zhǎng)流程時(shí)間,最長(zhǎng)流程時(shí)間（加工周期）：從第一個(gè)工件在第一臺(tái)機(jī)器上加工起到最后一個(gè)工件在最后一臺(tái)機(jī)器上加工完畢為止所經(jīng)過的時(shí)間。假定所有工件的到達(dá)時(shí)間都為0，則Fmax等于排在末位加工的工件在車間的停留時(shí)間。,二、最長(zhǎng)流程時(shí)間,計(jì)算Fmax的幾個(gè)假定條件：機(jī)器M1不會(huì)發(fā)生空閑；對(duì)其它機(jī)器，能對(duì)某一工件加工必須具備2個(gè)條件：機(jī)器必須完成排前一位的工件的加工；要加工的工件的上道工序已經(jīng)完工。,二、最長(zhǎng)流程時(shí)間,二、最長(zhǎng)流程時(shí)間,,,,,,,,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在機(jī)器M1上的加工時(shí)間，bi為工件Ji在機(jī)器M2上的加工時(shí)間，每個(gè)工件按M1—M2的路線加工。,三、n/2/F/Fmax問題的算法,Johnson算法的步驟：從加工時(shí)間矩陣中找出最短的加工時(shí)間。若最短時(shí)間出現(xiàn)在M1上，則對(duì)應(yīng)的工件盡可能往前排。若最短時(shí)間出現(xiàn)在M2上，則對(duì)應(yīng)的工件盡可能往后排。若最短時(shí)間有多個(gè)，則任選一個(gè)。劃去已排序的工件。若所有工件都已排序，則停止，否則重復(fù)上述步驟。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,對(duì)于一般的n/m/P/Fmax問題，可以用分支定界法求得最優(yōu)解，但計(jì)算量很大。實(shí)際中，可以用啟發(fā)式算法求近優(yōu)解。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,1、Palmer法計(jì)算工件斜度指標(biāo)?i：m:機(jī)器數(shù)pik：工件i在機(jī)器k上的加工時(shí)間。i=1,2,?,n排序方法:按?i從大到小的順序排列。按排序的順序計(jì)算Fmax,四、一般n/m/P/Fmax問題的啟發(fā)式算法,2、關(guān)鍵工件法：計(jì)算Pi=?Pij，找出Pi最長(zhǎng)的工件，將之作為關(guān)鍵工件C。對(duì)其余工件，若Pi1≤Pim，則按Pi1由小到大排成序列SA。若Pi1>Pim，則按Pim由大到小排成序列SB。順序（SA，C，SB）即為近優(yōu)解。,四、一般n/m/P/Fmax問題的啟發(fā)式算法,得到的加工順序?yàn)?1，2，3，4),四、一般n/m/P/Fmax問題的啟發(fā)式算法,3、CDS法：CDS法是Johnson算法的擴(kuò)展方法，從M-1個(gè)排序中找出近優(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道工序是在機(jī)器k上進(jìn)行。加工描述矩陣D：每一行描述一個(gè)工件的加工，每一列的工序序號(hào)相同。,五、單件車間排序問題（n/m/G/Fmax）,加工時(shí)間矩陣T：與D相對(duì)應(yīng)。,,五、單件車間排序問題（n/m/G/Fmax）,加工順序矩陣S：每一行與機(jī)器相對(duì)應(yīng)，每一列與工件相對(duì)應(yīng)。,,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、能動(dòng)作業(yè)計(jì)劃的構(gòu)成各工序都按最早可能開(完)工時(shí)間安排且任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序。符號(hào)說明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序構(gòu)成的部分作業(yè)計(jì)劃Tk{Ot}中工序Ok的最早可能開工時(shí)間T’k{Ot}中工序Ok的最早可能完工時(shí)間,五、單件車間排序問題（n/m/G/Fmax）,能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟：①設(shè)t＝1，{St}為空，{Ot}為各工件第一道工序的集合。②求最小的最早完工時(shí)間T*=min{T’k},并找到出現(xiàn)T*的機(jī)器M*，若有多臺(tái)，任選一臺(tái)。③從{Ot}中跳出滿足以下兩條件的工序Oj需要機(jī)器M*加工；Tj下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁(yè)未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 作業(yè) 排序 生產(chǎn)管理 華中科技大學(xué) 南方
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://www.hcyjhs8.com/p-11519806.html