【摘要】：針對以總完工時間與總外包費用加權(quán)和為優(yōu)化目標、總外包費用不超過給定上限的單機單轉(zhuǎn)包商調(diào)度與外包聯(lián)合優(yōu)化問題,設(shè)計出一種改進的剔除型啟發(fā)式算法。該算法通過運用動態(tài)規(guī)劃技術(shù)求解新的輔助問題來獲取初始外包工件集,并引入判定條件提前從初始外包工件集中剔除特定工件。為滿足對總外包費用的上限約束,還利用新型的啟發(fā)式篩選次序族逐一確定從當前外包工件集中剔除的工件。在仿真實驗中,通過生成大量的測試算例,對比分析了改進算法與另2種已報道算法在求解質(zhì)量、計算時間上的表現(xiàn)情況。實驗結(jié)果表明所提出的改進算法在解的整體質(zhì)量上具備顯著的比較優(yōu)勢,并且能在5.6秒內(nèi)完成對工件總數(shù)為1500的測試算例的求解。
[Abstract]:Based on the weighted sum of total completion time and total outsourcing cost, an improved elimination heuristic algorithm is designed to solve the joint optimization problem of single machine and single subcontractor scheduling and outsourcing with the total outsourcing cost less than the given upper limit. The algorithm uses dynamic programming technology to solve new auxiliary problems to obtain the initial outsourced workpiece set, and introduces the decision condition to remove the specific workpiece from the initial outsourced workpiece set in advance. In order to meet the upper bound of the total outsourced cost, a new heuristic screening suborder family is used to determine the jobs that are removed from the current outsourced job set one by one. In the simulation experiment, by generating a large number of test examples, the performance of the improved algorithm and the other two reported algorithms in solution quality and calculation time are compared and analyzed. The experimental results show that the proposed improved algorithm has significant comparative advantages in the overall quality of the solution and can be used to solve the test example with the total number of workpiece 1500 in 5.6 seconds.
【作者單位】： 濟南大學商學院;
【基金】：國家自然科學基金青年項目(71501083) 教育部人文社科研究青年基金資助項目(14YJCZH098) 山東省優(yōu)秀中青年科學家科研獎勵基金資助項目(BS2015ZZ002) 濟南大學科研基金資助項目(XKY1322)
【分類號】：TP301.6

【相似文獻】

相關(guān)期刊論文 前10條

1 毛道曉;徐克林;張志英;侯麗清;;越庫中心選址模型與啟發(fā)式算法[J];中南大學學報(自然科學版);2013年02期

2 李克文,吳孟達,張雄明;約簡的一種啟發(fā)式算法[J];計算機工程與科學;2004年01期

3 宋萬忠;;一種改進的多機場地面等待啟發(fā)式算法[J];計算機應用;2007年S1期

4 周旭東;王麗愛;陳];;啟發(fā)式算法求解最大團問題研究[J];計算機工程與設(shè)計;2007年18期

5 李亞志;朱夏;;基于插入-分段的無等待流水作業(yè)調(diào)度復合啟發(fā)式算法[J];東南大學學報(自然科學版);2013年03期

6 唐立新;祁慧;楊自厚;王夢光;;基于P-中位模型的聚類分析的拉格朗日啟發(fā)式算法[J];模式識別與人工智能;1997年01期

7 張潛,高立群,劉雪梅,胡祥培;定位-運輸路線安排問題的兩階段啟發(fā)式算法[J];控制與決策;2004年07期

8 黃志,黃文奇;作業(yè)車間調(diào)度問題的一種啟發(fā)式算法[J];計算機工程與應用;2004年26期

9 袁俊斌;蘇慶忠;;基于啟發(fā)式算法的物流配送中心選址研究[J];價值工程;2009年11期

10 戴香糧;王映龍;;混合啟發(fā)式算法在汽車調(diào)度中的應用[J];電子技術(shù)應用;2009年07期

相關(guān)會議論文 前5條

1 劉嘉敏;馬廣煜;黃有群;;基于組合的三維集裝箱裝入啟發(fā)式算法的研究[A];全國第13屆計算機輔助設(shè)計與圖形學（CAD/CG）學術(shù)會議論文集[C];2004年

2 劉金朋;魏長江;;啟發(fā)式算法求最短路徑的一種高效率實現(xiàn)方法[A];2007北京地區(qū)高校研究生學術(shù)交流會通信與信息技術(shù)會議論文集（上冊）[C];2008年

3 范敏;鄒平;朱興東;;一種啟發(fā)式離散化算法及其Delphi實現(xiàn)[A];第二屆中國智能計算大會論文集[C];2008年

4 馮德鴻;唐加福;郭琦;李輝;;訂貨批量問題改進的相關(guān)策略啟發(fā)式算法與仿真分析[A];2007系統(tǒng)仿真技術(shù)及其應用學術(shù)會議論文集[C];2007年

5 李兵;吳孟達;;信息系統(tǒng)中一種基于屬性相對重要度的啟發(fā)式約簡算法[A];中國系統(tǒng)工程學會模糊數(shù)學與模糊系統(tǒng)委員會第十一屆年會論文選集[C];2002年

相關(guān)重要報紙文章 前1條

1 本報記者 劉華;金融危機為成都接包商帶來重大機遇[N];成都日報;2008年

相關(guān)博士學位論文 前5條

1 賴向京;原子團簇結(jié)構(gòu)預測的現(xiàn)實途徑—高性能啟發(fā)式算法[D];華中科技大學;2012年

2 黎展滔;具有成組約束的柔性流水車間作業(yè)計劃制定的啟發(fā)式算法[D];廣東工業(yè)大學;2012年

3 董興業(yè);啟發(fā)式算法及其在同順序流水作業(yè)問題中的應用[D];北京交通大學;2008年

4 古繼興;KOD多播技術(shù)與Steiner樹啟發(fā)式算法[D];上海交通大學;2007年

5 任志磊;組合優(yōu)化問題的特化與泛化算法設(shè)計[D];大連理工大學;2013年

相關(guān)碩士學位論文 前10條

1 周書橙;護士排班的啟發(fā)式算法研究與排班管理系統(tǒng)的設(shè)計實現(xiàn)[D];北京交通大學;2016年

2 劉賽賽;基于增強學習的啟發(fā)式和元啟發(fā)式搜索的參數(shù)調(diào)優(yōu)策略[D];電子科技大學;2016年

3 劉志宏;合同組批系統(tǒng)中優(yōu)化算法的研究[D];東北大學;2013年

4 陳濤;基于大數(shù)據(jù)和混合啟發(fā)式算法的公交調(diào)度方法[D];杭州電子科技大學;2016年

5 劉永凱;課表安排問題的啟發(fā)式算法研究[D];廈門大學;2009年

6 陳雪瑛;基于啟發(fā)式算法的庫存路徑優(yōu)化問題研究[D];北京交通大學;2008年

7 陳敏;基于啟發(fā)式算法的合同組批系統(tǒng)研究與設(shè)計[D];東北大學;2012年

8 于U，

本文編號：2431561