【正文】 于單件 訂貨型生產(chǎn)。 其次 ,探索了基于啟發(fā) 式調(diào)度規(guī)則的車間作業(yè)計(jì)劃問題的求解 ,研究和設(shè)計(jì)了啟發(fā)式 調(diào)度算法 ,并采用面向?qū)ο蟮木幊陶Z言、基于開發(fā)平臺(tái) ,進(jìn)行了仿真調(diào)度平 臺(tái)的設(shè)計(jì)和擴(kuò)充。在工業(yè)發(fā)達(dá)國家約占其整個(gè)國民生產(chǎn)總值的 %以 上 ,發(fā)展程度體現(xiàn)了一個(gè)國家的綜合國力和科技水平。因此 ,在制造業(yè)企業(yè)經(jīng)常出現(xiàn)這樣一種狀況 , 車間的制造系統(tǒng)近似一個(gè)“黑箱 ,管理人員無法掌握工件的加工進(jìn)度 ,等某一個(gè)或幾個(gè) 工件臨近交貨期時(shí) ,將制造資源集中地投入到這一個(gè)或幾個(gè)工件加班加點(diǎn) ,這樣 其他工 件生產(chǎn)受到影響又進(jìn)一步成為“急救的對(duì)象。此 后 ,有關(guān)于此的分析和討論層出不窮 ,有軟件系統(tǒng)本身的原因、企業(yè)的原因、實(shí)施的原因 等等。車間作業(yè)計(jì)劃用來直接指導(dǎo)車間的加工作業(yè) ,就是負(fù)責(zé)底層控制 ,即直接負(fù) 責(zé)車間級(jí)調(diào)度執(zhí)行和生產(chǎn)管理。它具有非常重要的理論和實(shí)際研究價(jià)值 ,引起了理 論和工程界廣泛的關(guān)注和研究【‘。 .和 ..在年提出了用于車間作業(yè)調(diào)度問題一組基于優(yōu)先分派規(guī)則的啟發(fā)式算法。從對(duì)極其棘手的車間作業(yè)調(diào)度問題復(fù)雜性的大量的研究工作中 ,人們發(fā)現(xiàn)僅有少量特 殊實(shí)例可以在多項(xiàng)式時(shí)間內(nèi)解決。用神經(jīng)網(wǎng)絡(luò)解決調(diào) 度問題是另一種迭代近似方法 ,雖然神經(jīng)網(wǎng)絡(luò)有著分布處理問題的能力 ,但它在解決問題 時(shí)有著較大的計(jì)算負(fù)擔(dān)。為此本 文提出“基于啟發(fā)式調(diào)度規(guī) 則的動(dòng)態(tài)車間作業(yè)計(jì)劃算法及仿真研究’’課題 ,具體針對(duì)相應(yīng)的動(dòng)態(tài)車間作業(yè)計(jì)劃仿真系 統(tǒng)模型 ,研究了車間作業(yè)計(jì)劃算法 ,為啟發(fā)式調(diào)度規(guī)則在車間級(jí)的生產(chǎn)調(diào)度問題中的應(yīng)用 和推廣奠定基礎(chǔ)。因此 ,將具體 針對(duì)以上三個(gè)方面設(shè)計(jì)車間作業(yè)計(jì)劃問題的仿真調(diào)度案例。其內(nèi)容不 僅包 括確定工件的加工順序 ,而且還要確定機(jī)器加工每個(gè)工件的開始和完成時(shí)間。通常是 多約束、多目標(biāo)、隨機(jī)不確定優(yōu)化問題 ,其共有的特點(diǎn)和存在的問題如下 : 復(fù)雜性。因此 ,不同目標(biāo)之間的沖突 ,進(jìn)一步增加車間作業(yè)計(jì)劃問 題的難度。而事實(shí)上 ,調(diào)度環(huán)境和任務(wù)存在著不可預(yù)測的擾動(dòng)情況下的調(diào)度方案 ,它不僅依賴 于事前調(diào)度環(huán)境和任務(wù) ,而且與當(dāng)前狀態(tài)有關(guān) ,則為動(dòng)態(tài)調(diào)度【。在流水車間作業(yè)計(jì)劃問題中 ,包括多 臺(tái)機(jī)器 ,每個(gè)任務(wù)包括多個(gè)操作 ,所有任務(wù)所包括的操作順序是相同的即相當(dāng)于具有相同 的工藝路線。各工件互相獨(dú)立 ,投放時(shí)間為零 ,不存在交 貨期約束。調(diào)度問 題的目標(biāo)函數(shù)是求個(gè)工件的最優(yōu)加工順序 ,使最大流經(jīng)時(shí)間最小。 經(jīng)典 的單件車間作業(yè)計(jì)劃問題的數(shù)學(xué)問題描述為 :設(shè)該系統(tǒng)生產(chǎn) ,個(gè)工件 ,表示為集 合 ,?,刀 ,生產(chǎn)系統(tǒng)內(nèi)有朋臺(tái)機(jī)器 ,表示為集合 ,?,聊 ,每個(gè)工件需要經(jīng)過碩士學(xué)位論文 第頁 武漢科技大學(xué) 若干個(gè)工序完成 ,若磕表示第個(gè)工件的射道工序在第臺(tái)機(jī)器上加工的工序 ,其開始加 工時(shí)間和需要加工的時(shí)間分別記為 %和 %。車間作業(yè)計(jì)劃問題采用整數(shù)線性規(guī)劃模型描述為 : ∈ . 朋瓦。 對(duì)每個(gè)操作均允許等待。 機(jī)器之外的其他資源無限制 。 近似算法包括 :構(gòu)造方法、鄰域搜索方法和人工智能方法。這類方法能夠快速構(gòu)造解 ,但優(yōu)化質(zhì)量一般較差。該類方法利用人工智能的原理和技術(shù)進(jìn)行搜索 ,譬如將優(yōu)化 過程轉(zhuǎn)化為智能系統(tǒng)動(dòng)態(tài)的演化過程 ,基于系統(tǒng)動(dòng)態(tài)的演化來實(shí)現(xiàn)優(yōu)化。 因此 ,考慮到車 間作業(yè)計(jì)劃問題的復(fù)雜性和規(guī)模 ,目前最為實(shí)用而有效的算法仍然是 啟發(fā)式調(diào)度規(guī)則算法。對(duì)于強(qiáng)困難的調(diào)度問 車間作業(yè)調(diào)度問題是強(qiáng)困難 問題百 題 ,從實(shí)際系統(tǒng)的復(fù)雜性、規(guī)模性和可操作性角度考慮 ,啟發(fā)式調(diào)度規(guī)則仍然是目前最可 行和有效的求解方法。 機(jī)器集 :似 ,?,?,。 :當(dāng)前時(shí)間 ,即是進(jìn)行調(diào)度決策的時(shí)刻 。 , 規(guī)貝 :規(guī)則為“工件到達(dá)時(shí)間越早越優(yōu)先’’。顯然 , 也是基于加工工時(shí)的規(guī)則。一妻粕 / 驢彳 ?/島 , 互 : . ∑ %一 .,/墨 √ . 規(guī)貝 :規(guī)則可表述為“工件的交貨期越早越優(yōu)先 ,顯然 , 規(guī)則是基于交貨期的規(guī)則。設(shè) 工件以當(dāng)前等待加工的工序?yàn)?,在調(diào)度時(shí)刻工件‘的優(yōu)先數(shù)定義為 : 嘞 . 吩 Ⅳ 【 %?幽哪 /規(guī)貝 .: /規(guī)則是 規(guī)則與規(guī)則相除得到組合規(guī)則 , 設(shè)工件以當(dāng)前等待加工的工序?yàn)?,在調(diào)度時(shí)刻工件以的優(yōu)先數(shù)定義為 : 珞 驢“一‘ . /% 互驢 .薈篡 .“一‘ ,規(guī)則 :該規(guī) 則為由、和相加形成的組合規(guī)則。已有文 獻(xiàn)中對(duì)調(diào)度規(guī)則 于不同調(diào)度問題的調(diào)度效果進(jìn)行了大量的研究 ,提供了一些具有參考和指 導(dǎo)價(jià)值的研究結(jié)果。 .提出的 規(guī)則和規(guī)則 組成的隨機(jī)規(guī)則通過仿真實(shí)驗(yàn)表明對(duì)于最小化平均流經(jīng)時(shí)間的單件車間作業(yè)計(jì)劃問題其 優(yōu)化性能大大優(yōu)于規(guī)則和。 已有的調(diào)度規(guī)則 及對(duì)其性能評(píng)價(jià)的研究結(jié)果對(duì)于調(diào)度規(guī)則使用中的選擇、新調(diào)度規(guī)則 的設(shè)計(jì)具有一定的指導(dǎo)意義。加權(quán)法柏】。此外 ,它們 始終存在如下關(guān)系 :. 定義可調(diào)度工序 。根據(jù)啟發(fā)式調(diào)度算法的思想 ,設(shè)計(jì)啟發(fā)式算法的總體調(diào)度 流程如下 : :令調(diào)度時(shí)刻為 :‘ ,意味著調(diào)度 的開始時(shí)刻。為可調(diào)度工序集瓦中按相應(yīng)的啟發(fā)式或優(yōu)先調(diào)度規(guī) 則具有最高優(yōu)先級(jí)的工序。廣 :更新己調(diào)度工序集、可調(diào)度工序集和不可調(diào)度工序集為如下 :碩士學(xué)位論文 第頁 武漢科技大學(xué) . 、 吼睥 , ‘ ●。 凈。 .算法的編程實(shí)現(xiàn) .. 語言及開發(fā)環(huán)境 是鋤公司開發(fā)的一種面向?qū)ο蟮某绦蛟O(shè)計(jì)語言 ,是一個(gè)基于 語言的平臺(tái) ,這個(gè)建立在操作系統(tǒng)之上的平臺(tái)能夠提供企業(yè)級(jí)服務(wù)、通用服務(wù)、無線服務(wù) 以及智能卡服務(wù)。色一 句研。以下對(duì)該五個(gè)關(guān)鍵類及其方法進(jìn)行簡略介紹。該類的 模型如圖 所示。主 要方法為 。其模型如圖 .所示。 。 .。 。 。 。 。 。 。 一車間中的機(jī)器集合 。 蓋摹萄羞羞函 ?ⅡⅢ目 .? 一一一一一 ? 薹三強(qiáng)童島巨晶 妻里三垂丑 二面 日 一三二一。在該類的方中 ,啟動(dòng)對(duì)仿 真調(diào)度算法的主控類的調(diào)用。 ,或屯 , 引 %,引 %. 是 結(jié)束 圖 .啟發(fā)式算法流程圖 調(diào)用相應(yīng)的啟發(fā)式調(diào)度規(guī)則和調(diào)度結(jié)果輸出到數(shù)據(jù)庫等編程 ,在下一節(jié)將主要針 對(duì)所提到的算法關(guān)鍵類的設(shè)計(jì)進(jìn)行詳細(xì)介紹。 由此 ,基于的開發(fā)是現(xiàn)在軟件業(yè)的一大主流 ,所以很多公司都投入到的集成開發(fā) 環(huán)境的研發(fā)中 , 公司出品的就是其中最優(yōu)秀的開發(fā)工具之一。 ,。記受工序啡 ,影響的工序?yàn)猷?,則 :%%邢戶一 ? 同時(shí)更新受工序啡 ,。戶 。 :根據(jù)工件的投放時(shí)間、交貨期、工藝路線、工序的工時(shí)等計(jì)算工序的最早可開 工時(shí)間『和最遲須完工時(shí)間。武漢科技大學(xué) 碩士學(xué)位論文 第頁 定義可調(diào)度工序集瓦 ,、不可調(diào)度工序集幺 :所有‘時(shí)刻可調(diào)度工序的集合稱為‘ 時(shí)刻的可調(diào)度工序集 ,記為瓦 。時(shí)刻未調(diào)度工 序 ,記為魂。隨機(jī)組合法?！?/規(guī)則碩士學(xué)位論文 第頁 武漢科技大學(xué) 和 /規(guī)則在許多制造系統(tǒng)中對(duì)于流經(jīng)時(shí)間相關(guān)的性能指標(biāo)問題具有較好效果。規(guī)則對(duì)最小化最大流經(jīng)時(shí)間和流經(jīng)時(shí)間 方差具有優(yōu)越的 性能。如果≤ .,采用規(guī)則進(jìn)行調(diào)度。 .【刀等首次利用調(diào)度規(guī)則對(duì)離散事 件進(jìn)行分析和仿真 ,同樣也得出沒有一種簡單規(guī)則能使所有的調(diào)度性能達(dá)到最優(yōu)。的優(yōu)先數(shù)定義為 : 互∑ % . 規(guī)則鶴 規(guī)則 為“松弛時(shí)間越小越優(yōu)先。在調(diào)度時(shí) 刻的優(yōu)先數(shù)定義為 : 互礦 . 規(guī)貝 :規(guī)則為“在系統(tǒng)中的時(shí)間越長越優(yōu)先 ,工件以在調(diào) 度時(shí)刻的優(yōu)先數(shù)定義為 : . 互一 ,。 由于調(diào)度規(guī)則的性能受到各種參數(shù)如 :車間的機(jī)器利用率、交貨期寬裕度系數(shù)、調(diào)度 性能指標(biāo)等的影響 ,迄今為止 ,尚無任何一個(gè)調(diào)度規(guī)則能夠在任意的車間調(diào)度問題中表現(xiàn) 出良好的調(diào)度性能啊。 ,?,刀 ,?,。 .啟發(fā)式調(diào)度規(guī)則 ..啟發(fā)式調(diào)度規(guī)則的分類 啟發(fā)式規(guī)則用于選擇下一道在當(dāng)前空閑機(jī)器上將進(jìn)行加工的工序。因此 ,在接下來將對(duì)啟發(fā)式調(diào)度規(guī)則 的性能進(jìn)行分析。而神經(jīng)網(wǎng)路和蟻群系統(tǒng)等方法優(yōu)化時(shí)間性能較差 ,而優(yōu)化質(zhì)量嚴(yán)重依賴于網(wǎng)路參數(shù) , 甚至可能產(chǎn)生非法調(diào)度。它是動(dòng)態(tài)調(diào)度的典型 ,對(duì)于實(shí)際生產(chǎn)系統(tǒng)中 ,復(fù)雜的大規(guī)模的車間 作業(yè)計(jì)劃來說 ,具 有很大的優(yōu)越性。枚舉法是隱含枚舉整個(gè)空間的搜索方法 ,搜索效率低 ,但求解實(shí)際問題的 計(jì)算量太大。 按照車間作業(yè)計(jì)劃問題的特點(diǎn)及分類 ,依據(jù)本文研究的對(duì)象單件訂貨型企業(yè)的車間級(jí) 作業(yè)調(diào)度 ,文中研究的車間作業(yè)計(jì)劃問題即是指開環(huán)動(dòng)態(tài)基于調(diào)度性能的單件車間作業(yè)計(jì) 劃問題。 對(duì)機(jī)器的假定包括 : 在從加工過程開始的計(jì)劃時(shí)間內(nèi) ,所有臺(tái)機(jī)器均為有效的。 每一個(gè)操作限定為不能由多于一臺(tái)的機(jī)器來進(jìn)行加工 。工件的投放時(shí)間和交貨期分別記為和西 。 工序的準(zhǔn)備時(shí)間與順序無關(guān) ,且包含在加工時(shí)間中。要求將工件集 /分派到機(jī)器集上 ,并且確定加工次序 ,使 得某項(xiàng)目標(biāo)達(dá)到最優(yōu)。顯然 ,平行機(jī)調(diào)度問題和流水車間作業(yè)計(jì)劃問題均是單件車間作業(yè)計(jì)劃問題是特 例。相對(duì)地 ,在多機(jī)調(diào)度問題 中 ,操作任務(wù)需要在多 臺(tái)機(jī)器上完成。采用動(dòng)態(tài)調(diào)度可在一定程度上克服隨機(jī)性帶來的影響。 多目標(biāo)性。有些約束條件是必須滿足的 ,如交貨期、生產(chǎn)能力 , 而 有些達(dá)到一定的滿意度即可 ,如生產(chǎn)成本。 全文的技術(shù)路線 如圖 .所示。 第三章對(duì)進(jìn)一步對(duì)車間作業(yè)計(jì)