生產(chǎn)運(yùn)作管理制造業(yè)作業(yè)計(jì)劃與控制課件-文庫(kù)吧資料
2025-02-12 22:59本頁(yè)面
【正文】 ? （ 4）將選定的工序 Oj放入 {St},從 {Ot}中消去 Oj,并將 Oj的緊后工序放入 {Ot} ，使 t=t+1。 如果 M*有多臺(tái)，則任選一臺(tái)。 能動(dòng)作業(yè)計(jì)劃的構(gòu)成 2,3,2 M2 13 13 8 2,3,2 6 1,3,2 M2 8 8 12 7 7 1,3,2 2,3,2 5 2,2,1 M1 7 8 7 7 3 1,3,2 2,2,1 4 1,2,3 M3 7 7 7 3 3 1,2,3 2,2,1 3 2,1,3 M3 3 6 3 2 0 1,2,3 2,1,3 2 1,1,1 M1 2 2 3 0 0 1,1,1 2,1,3 1 Oj M* T* T`k Tk {Ot} t 能動(dòng)作業(yè)計(jì)劃的甘特圖 2,3,2 1,1,1 2,2,1 1,3,2 2,1,3 1,2,3 3 7 7 8 13 2 3 7 0 時(shí)間 機(jī)器 M1 M2 M3 （二）無(wú)延遲作業(yè)計(jì)劃構(gòu)成步驟 ? （ 1）設(shè) t=1,{S1}為空集， {O1}為各工件第一道工序的集合。 ? （ 4）將選定的工序 Oj放入 {St},從 {Ot}中消去 Oj,并將 Oj的緊后工序放入 {Ot} ，使 t=t+1. ? （ 5）若還有未安排的工序，轉(zhuǎn)步驟（ 2）；否則，停止。 如果 M*有多臺(tái)，則任選一臺(tái)。 （一）能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟 ? （ 1）設(shè) t=1,{S1}為空集， {O1}為各工件第一道工序的集合。 ? 無(wú)延遲作業(yè)計(jì)劃是沒(méi)有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃。 兩種作業(yè)計(jì)劃的構(gòu)成 ? 各工序都按最早可能完工時(shí)間安排的作業(yè)計(jì)劃稱(chēng)為能動(dòng)作業(yè)計(jì)劃。 i表示工件代號(hào)， j表示工序號(hào)， k表示完成工序 i的第 j道工序的機(jī)器代號(hào)。 2142 289541013895421176)(?????????????????ijc????????????0673390245100954????????????01733402401004545 √ √ ????????????????1062340240101343????????????0062440250100343???????????????0100001000011000ijx√ 問(wèn)題的描述 加工描述矩陣 D為 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 對(duì)于一般單件作業(yè)排序問(wèn)題，每個(gè)工件都有其獨(dú)特的加工路線，工件沒(méi)有一定的流向。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。 ???????????????0100000100101000ijx????????????9118713161491514410413152????????????00102350960607130例 2 有 甲、乙、丙、丁 四個(gè)工人，要分別派他們完成四項(xiàng)不同的任務(wù)，分別記作 A、 B、 C、 D。 0 （ 2）若 獨(dú)立零元素 的數(shù)目 m等于矩陣的階數(shù) n，那么這指派問(wèn)題的最優(yōu)解已得到。 第 2步：進(jìn)行試指派，即確定獨(dú)立零元素 （ 1）從有唯一的零元素的行或列開(kāi)始確定獨(dú)立零元素，并用 表示，并劃掉其所在行或列的其他零。 j=1,2,3,4) 甲 乙 丙 丁 工作 人 譯英文 譯日文 譯德文 譯俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 指派問(wèn)題的匈牙利解法 ????????????9118713161491514410413152????????????241047501110062111302 4 9 7 第 1步：變換指派問(wèn)題的系數(shù)矩陣（ cij），使各行各列中都出現(xiàn) 0元素 (1) 從（ cij）的每行元素都減去該行的最小元素； (2)再?gòu)乃眯孪禂?shù)矩陣無(wú)零元素的列中減去該列的最小元素。規(guī)定每項(xiàng)工作只能交與其中的一個(gè)人完成，每個(gè)人只能完成其中的一項(xiàng)工作。j=… n)并假設(shè) Cij ≥ 0。 第三節(jié) 單件作業(yè)排序問(wèn)題 ? 指派問(wèn)題 ? 單件作業(yè)排序問(wèn)題的描述 ? 兩種作業(yè)計(jì)劃的構(gòu)成 ? 求解一般 n/m/G/Fmax問(wèn)題的啟發(fā)式方法 ? 指派問(wèn)題的形式表述 ? 給定了一系列所要完成的任務(wù)（ tasks）以及一系列完成任務(wù)的被指派者（ assignees），所需要解決的問(wèn)題就是要確定出哪一個(gè)人被指派進(jìn)行哪一項(xiàng)任務(wù) 指派問(wèn)題的假設(shè) ?被指派者的數(shù)量和任務(wù)的數(shù)量是 相同的 ?每一個(gè)被指派者只完成 一項(xiàng)任務(wù) ?每一項(xiàng)任務(wù)只能由 一 個(gè)被指派者 來(lái)完成 ?每個(gè)被指派者和每項(xiàng)任務(wù)的組合有一個(gè)相關(guān)成本 ?目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小 指派問(wèn)題 設(shè) n 個(gè)人被分配去做 n 件工作 ， 每人只能完成一項(xiàng)任務(wù) ， 每項(xiàng)任務(wù)只能由一人完成 。求三種移動(dòng)方式下的加工周期。 分鐘104 ?t 分鐘10?t 分鐘5t 分鐘153 ?t具體做法 ? （ 1）當(dāng) titi+1時(shí)，零件按平行移動(dòng)方式轉(zhuǎn)移； ? （ 2）當(dāng) ti≥t i+1時(shí)，以 i工序最后一個(gè)零件的完工時(shí)間為基準(zhǔn)，往前推移（ n1） ti+1作為零件在（ i+1）工序的開(kāi)始時(shí)間。為最長(zhǎng)的單件工序時(shí)間式中，平LLitt)1n(t ??? ?T已知 n=4， t1=10分鐘， t2=5分鐘， t3=15分鐘， t4=10分鐘，則 T平 =（ 10+5+15+10） +（ 41） 15=85分鐘 （三）平行順序移動(dòng)方式 ? 既要求每道工序連續(xù)進(jì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分鐘 （二）平行移動(dòng)方式 分鐘101 ?t 分鐘52 分鐘153t工序 1 2 3 4 時(shí)間 加工周期 每個(gè)零件在前道工序加工完畢后，立即轉(zhuǎn)移到后道工序去繼續(xù)加工，形成前后工序交叉作業(yè)。 ? 三種典型的移動(dòng)方式 – 順序移動(dòng)方式 (串行工程 ) – 平行移動(dòng)方式（平行工程） – 平行順序移動(dòng)方式 （一）順序移動(dòng)方式 分鐘52 ?t 分鐘153 ?t加工周期 時(shí)間 工序 1 2 3 4 順序移動(dòng)方式 一批零件在上道工序全部加工完畢后才整批地轉(zhuǎn)移到下道工序繼續(xù)加工。 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 四、相同零件、不同移動(dòng)方式下加工周期的計(jì)算 ? 排序問(wèn)題針對(duì)的是不同零件，如果 n個(gè)零件相同，則沒(méi)有排序問(wèn)題。 所以，取順序（ 1， 2， 3， 4）。和 1m21pml1mkik1????????lplkikm=2時(shí)， l=1,加工時(shí)間分別為 pi1和 pi2； m=3時(shí)， l=1,2,加工時(shí)間分別為 ： （ 1） l=1， pi1和 pi3 （ 2） l=2,pi1+pi2和 pi2+pi3 m=4時(shí)， l=1， 2， 3，加工時(shí)間分別為： （ 1） l=1,pi1和 pi4 （ 2） l=2， pi1+pi2和 pi3+pi4 （ 3） l=3， pi1+pi2+pi3和 pi2+pi3+pi4 l A 加工時(shí)間 B 加工時(shí)間 1 t 1 t m 2 t 1 +t 2 t m1 +t m 3 t 1 +t 2 +t 3 t m2 +t m1 +t m … …… …… m1 t 1 +t 2 + … +t m1 t 2 + … +t m 1 +t m i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 2)1(pml1mkik1，和 ??????lplkiki 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1+pi2 9 6 8 12 pi2+pi3 12 9 10 11 i 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1+pi2 9 6 8 12 pi2+pi3 12 9 10 11 當(dāng) l=1時(shí)，按（ Johnson）算法得到加工順序（ 1， 2， 3，4）； 當(dāng) l=2時(shí)，得到加工順序（ 2， 3， 1， 4）。 。 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 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 pi 16 24 17 19 （三） CDS法 ? 康坎貝爾 杜德克 史密斯三人提出了一個(gè)啟發(fā)式算法，簡(jiǎn)稱(chēng) CDS法。 例 題 ? 用關(guān)鍵工件法求解下表的最優(yōu)排序。 i 1 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1