【文章內(nèi)容簡介】 /P/Fmax問題的最優(yōu)解，并比較三種方法的結(jié)果。 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6 2 3 7 四、相同零件、不同移動方式下加工周期的計算 ? 排序問題針對的是不同零件，如果 n個零件相同，則沒有排序問題。但零件在加工過程中采取的移動方式不同，會導(dǎo)致一批零件的加工周期不同。 ? 三種典型的移動方式 – 順序移動方式 (串行工程 ) – 平行移動方式（平行工程） – 平行順序移動方式 （一）順序移動方式 分鐘52 ?t 分鐘153 ?t加工周期 時間 工序 1 2 3 4 順序移動方式 一批零件在上道工序全部加工完畢后才整批地轉(zhuǎn)移到下道工序繼續(xù)加工。 分鐘101t 分鐘104t 設(shè)零件批量為 n（件），工序數(shù)目為 m，一批零件不計算工序間運輸時間，只考慮加工時間，設(shè)其加工的周期為 T（分鐘），零件在 i道工序的單件工時為 ti （分鐘 /件）， i=…n 。 則該批零件的加工周期為： 121... mimiT nt nt nt n t?? ? ? ? ? 已知 n=4， t1=10分鐘， t2=5分鐘， t3=15分鐘，t4=10分鐘，則 T順 =4 （ 10+5+15+10） =160分鐘 （二）平行移動方式 分鐘101 ?t 分鐘52 分鐘153t工序 1 2 3 4 時間 加工周期 每個零件在前道工序加工完畢后，立即轉(zhuǎn)移到后道工序去繼續(xù)加工，形成前后工序交叉作業(yè)。 分鐘104 ?t零件平行移動的加工周期 為： T 平 。為最長的單件工序時間式中，平LLitt)1n(t ??? ?T已知 n=4， t1=10分鐘， t2=5分鐘， t3=15分鐘， t4=10分鐘，則 T平 =（ 10+5+15+10） +（ 41） 15=85分鐘 （三）平行順序移動方式 ? 既要求每道工序連續(xù)進(jìn)行加工，又要求各道工序盡可能平行地加工。 時間 工序 1 2 3 4 加工 周期 （ 1）當(dāng) titi+1時，零件按平行移動方式轉(zhuǎn)移； （ 2）當(dāng) ti≥t i+1時，以i工序最后一個零件的完工時間為基準(zhǔn)，往前推移（ n1） ti+1作為零件在（ i+1）工序的開始時間。 分鐘104 ?t 分鐘10?t 分鐘5t 分鐘153 ?t具體做法 ? （ 1）當(dāng) titi+1時，零件按平行移動方式轉(zhuǎn)移； ? （ 2）當(dāng) ti≥t i+1時，以 i工序最后一個零件的完工時間為基準(zhǔn)，往前推移（ n1） ti+1作為零件在（ i+1）工序的開始時間。 平行順序移動加工周期計算 已知 n=4， t1=10分鐘， t2=5分鐘， t3=15分鐘， t4=10分鐘，則 T平順 =4 （ 10+5+15+10） （ 41） （ 5+5+10） =100分鐘 )tt(min)1n(tn 1j1m1jjm1ii ?????? ??? ，平順T? [例 ]已知 n=4， t1=10分鐘， t2=5分鐘， t3=15分鐘， t4=10分鐘。求三種移動方式下的加工周期。 ? 解： T順 =4 （ 10+5+15+10） =160分鐘 ? T平 =（ 10+5+15+10） +（ 41） 15=85分鐘 ? T平順 =4 （ 10+5+15+10） （ 41） （ 5+5+10） =100分鐘 比較項目 平行移動 平行順序移動 順序移動 生產(chǎn)周期 短 中 長 運輸次數(shù) 多 中 少 設(shè)備利用 差 好 好 組織管理 中 復(fù)雜 簡單 零件三種移動方式的比較 ? 已知 m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分別求在順序移動、平行移動和平行順序移動方式下，這批零件的加工周期。 第三節(jié) 單件作業(yè)排序問題 ? 指派問題 ? 單件作業(yè)排序問題的描述 ? 兩種作業(yè)計劃的構(gòu)成 ? 求解一般 n/m/G/Fmax問題的啟發(fā)式方法 ? 指派問題的形式表述 ? 給定了一系列所要完成的任務(wù)（ tasks）以及一系列完成任務(wù)的被指派者（ assignees），所需要解決的問題就是要確定出哪一個人被指派進(jìn)行哪一項任務(wù) 指派問題的假設(shè) ?被指派者的數(shù)量和任務(wù)的數(shù)量是 相同的 ?每一個被指派者只完成 一項任務(wù) ?每一項任務(wù)只能由 一 個被指派者 來完成 ?每個被指派者和每項任務(wù)的組合有一個相關(guān)成本 ?目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小 指派問題 設(shè) n 個人被分配去做 n 件工作 ， 每人只能完成一項任務(wù) ， 每項任務(wù)只能由一人完成 。 已知第 i 個人去做第 j 件工作的的效率為 Cij(i=… n。j=… n)并假設(shè) Cij ≥ 0。 問應(yīng)如何分配才能使總效率 （ 時間或費用 ） 最高 ？ )..,1(0)..( 1)..( 1m i n111 1njixnjxnixxcZijniijnjijninjijij????????????? ???? ?或指派問題模型 （ The Model for Assignment Problem） ??????項任務(wù)個人取完成第不分配第項任務(wù)個人取完成第分配第ji0ji1ijx典型問題 例 1：有一份說明書，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個人去完成，因各人專長不同，他們完成翻譯不同文字所需要的時間（小時）如表所示。規(guī)定每項工作只能交與其中的一個人完成，每個人只能完成其中的一項工作。 問：如何分配，能使所需的總時間最少？ 甲 乙 丙 丁 工作 人 譯英文 譯日文 譯德文 譯俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 建立模型 設(shè) xij= 1 0 若第 i項工作交與第 j個人完成 若第 i項工作不交與第 j個人完成 ? ?? ??4141mini jijij xcf譯英文： x11+ x12 + x13 + x14 =1 譯日文： x21+ x22 + x23 + x24 =1 譯德文： x31+ x32 + x33 + x34 =1 譯俄文： x41+ x42 + x43 + x44 =1 甲： x11+ x21 + x31 + x41 =1 乙： x12+ x22 + x32 + x42 =1 丙： x13+ x23 + x33 + x43 =1 丁： x14+ x24 + x34 + x44 =1 xij =0或 1 (i=1,2,3,4。 j=1,2,3,4) 甲 乙 丙 丁 工作 人 譯英文 譯日文 譯德文 譯俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 指派問題的匈牙利解法 ????????????9118713161491514410413152????????????241047501110062111302 4 9 7 第 1步：變換指派問題的系數(shù)矩陣（ cij），使各行各列中都出現(xiàn) 0元素 (1) 從（ cij）的每行元素都減去該行的最小元素； (2)再從所得新系數(shù)矩陣無零元素的列中減去該列的最小元素。 4 2 ????????????00102350960607130 在變化后的效率矩陣中找盡可能多的獨立 0元素，若能找出 n個獨立 0元素，就以這 n個獨立 0元素對應(yīng)解矩陣 (xij)中的元素為 1，其余為 0，這就得到最優(yōu)解。 第 2步：進(jìn)行試指派，即確定獨立零元素 （ 1）從有唯一的零元素的行或列開始確定獨立零元素，并用 表示，并劃掉其所在行或列的其他零。直到盡可能多的零元素都被圈出和劃掉為止。 0 （ 2）若 獨立零元素 的數(shù)目 m等于矩陣的階數(shù) n，那么這指派問題的最優(yōu)解已得到。若 m n, 則轉(zhuǎn)入下一步。 ???????????????0100000100101000ijx????????????9118713161491514410413152????????????00102350960607130例 2 有 甲、乙、丙、丁 四個工人，要分別派他們完成四項不同的任務(wù)，分別記作 A、 B、 C、 D。他們完成各項任務(wù)所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？ 任務(wù) 人員 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 第 1步 ， 變換系數(shù)矩陣： 2142 289541013895421176)(?????????????????ijc????????????0673390245100954????????????01733402401004545 第 2步，確定獨立零元素 找到 3 個獨立零元素， 但 m = 3 n = 4 求解過程如下 第 3步，作最少的直線覆