【正文】 :17:4800:17Jan2331Jan23 ? 1越是無能的人，越喜歡挑剔別人的錯兒。 。 設(shè)： A、 B、 C為三臺機器，如果工件在三臺機器上的加工時間滿足以下條件，則可以轉(zhuǎn)化為兩臺機器的排序問題： min Ai=max Bi or min Ci = max Bi 定義： A’ i = Ai+ Bi , B’ i = Bi +Ci 例 : 考慮以下問題 . 5個工件由 3臺機器加工 , 作業(yè)時間見下表 . 求 : 總加工周期最短的作業(yè)順序 . 1 2 3 4 5 機器 A 44 913 821 627 532 機器 B 59 619 223 330 436 機器 C 817 1029 635 742 1153 解 : 檢查上表 , 發(fā)現(xiàn) : min Ai = 4 max Bi = 6 min Ci = 6 因此 ,滿足以上條件 , 建立兩臺機器的作業(yè)時間表 : 應(yīng)用 Johnson法則，得出： １－４－５－２－３ 總加工周期為： 1 2 3 4 5 機器 A’ 9 15 10 9 9 機器 B’ 13 16 8 10 15 1 4 5 2 3 機器 A 44 610 515 924 832 機器 B 59 313 419 630 234 機器 C 817 724 1135 1045 651 m(m?3)臺機器排序問題的算法 （ N） ? 一般采用啟發(fā)式算法 (Heuristics)解決這類問題。 機器 1 到達系統(tǒng)工件的集合 離開系統(tǒng)（機器） J1 J2 J3 Jn 機器 2 兩臺機器排序問題的目標(biāo) ? 兩臺機器排序的目標(biāo)是使最大完成時間（總加工周期）Fmax最短。但是，編制作業(yè)計劃的主要工作之一就是要確定出最佳的作業(yè)順序。 確定出最佳的作業(yè)順序看似容易，只要列出所有的順序，然后再從中挑出最好的就可以了，但要實現(xiàn)這種想法幾乎是不可能的。 Fmax的含義見如下的甘特圖 (Gantt Chart)。 ? 關(guān)鍵工件法 步驟 1 計算 ,找出其中最大者，定義為關(guān)鍵工件 JC。 2023年 1月 上午 12時 17分 :17January 31, 2023 ? 1行動出成果，工作出財富。 00:17:4800:17:4800:17Tuesday, January 31, 2023 ? 1知人者智，自知者明。 00:17:4800:17:4800:171/31/2023 12:17:48 AM ? 1越是沒有本領(lǐng)的就越加自命不凡。 2023年 1月 31日星期二 上午 12時 17分 48秒 00:17: ? 1比不了得就不比，得不到的就不要。 但是，對于 n個工件由三臺機器流水作業(yè)時，在滿足某些條件后可以采用 Johnson’ s Law解決問題。 第 4節(jié) n項任務(wù)在兩臺機器的排序問題 兩臺機器排序問題的含義 n個工件都必須經(jīng)過機器 1和機器 2的加工，即工藝路線是一致的。 所以 ,編制作業(yè)計劃與排序的概念和目的都是不同的。 例如，考慮 32項任務(wù)（工件），有 32！ ??1035種方案 ,假定計算機每秒鐘可以檢查 1 billion個順序 , 全部檢驗完畢需要 ?1015個世紀(jì) . 如果只有 16個工件 , 同樣按每秒鐘可以檢查 1 billion個順序計算 , 也需要 2/3年 . 以上問題還沒有考慮其他的約束條件 , 如機器、人力資源、廠房場地等，如果加上這些約束條件，所需要的時間就無法想象了。 ? 多臺機器排序的目標(biāo)一般也是使最大完成時間（總加工周期） Fmax最短。 ??mj ijp1步驟 2 除 JC外，將滿足 pi1p1m的工件，按 ti1值的大小，從小到大排在 JC的前面。 2023年 1月 31日星期二 12時 17分 48秒 00:17:4831 January 2023 ? 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。勝人者有力，自勝者強。 , January 31, 2023 ? 閱讀一切好書如同和過去最杰出的人談話。 :17:4800:17:48January 31, 2023 ? 1他鄉(xiāng)生白發(fā)，舊國見青山。 兩臺機器排序問題算法的擴展 (N) 一般情況下，當(dāng)機器數(shù)為 3臺以上時，就很難找到最優(yōu)解了。 解：根據(jù) EDD原則，得出： J3 J5 J4J2 J1 加工時間 完成時間 交貨期 延遲 J3 31