發(fā)布時間：2018-11-18 11:28

【摘要】：研究工件既可以在制造商的同類機上加工,又可以一定費用分包給某承包商加工的排序決策問題·假設制造商有若干承包商,每個承包商有足夠多機器用于加工工件·制造商需要確定被分包的工件集,以及未分包工件的加工順序,使得工件最大完工時間與加工、分包費用線性和最小.證明問題的NP困難性,用數(shù)學規(guī)劃及組合方法設計了問題的近似算法,并分析算法性能比與漸近性.
[Abstract]:To study the sequencing decision problem in which the workpiece can be processed on the same machine of the manufacturer and can be subcontracted to a contractor at a certain cost, assuming that the manufacturer has several contractors, Each contractor has enough machines to process the workpiece the manufacturer needs to determine the set of subcontracted workpieces and the processing order of the unsubcontracted workpieces so that the maximum completion time of the workpiece and the processing time are linear and minimum subcontracting costs. The NP difficulty of the problem is proved. The approximate algorithm of the problem is designed by using mathematical programming and combinatorial method, and the performance ratio and asymptotic property of the algorithm are analyzed.
【作者單位】： 常州工學院數(shù)學系;上海第二工業(yè)大學管理工程研究所;
【基金】：國家自然科學基金(71371120)資助項目
【分類號】：O223

【相似文獻】

相關期刊論文 前10條

1 魏麒;蔣義偉;;一類兩階段雜交流水作業(yè)的近似算法(英文)[J];軟件學報;2012年05期

2 劉振宏;組合最優(yōu)化問題的近似算法[J];數(shù)學的實踐與認識;1983年03期

3 馬紹漢;一類限制樹問題的復雜性及其近似算法[J];山東大學學報(自然科學版);1984年01期

4 楊延齡,戚文發(fā);關于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學學報;1989年01期

5 杜林古;;帶風向投遞員問題的一個多項式1—近似算法[J];山東紡織工學院學報;1992年01期

6 何勇;帶核集分劃問題的一個線性(1/7)-近似算法[J];高校應用數(shù)學學報A輯(中文版);1997年04期

7 季敏,何勇;帶核集分劃問題的一個改進近似算法[J];系統(tǒng)工程理論與實踐;2003年12期

8 何曉瓊;陳沖;李榮珩;;工廠地址集中的k-種產(chǎn)品選址問題的近似算法[J];計算機工程與應用;2010年08期

9 李亮,葉尚輝;工程結構可靠性分析中高維概率積分的一種近似算法[J];應用力學學報;1989年02期

10 程建綱,秦成林;多處理機調(diào)度問題的一種近似算法[J];煙臺大學學報(自然科學與工程版);1997年03期

相關會議論文 前2條

1 梁國宏;郭云霞;鄭明發(fā);;最大化下模函數(shù)的近似算法及其性能保證[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學者大會論文集[C];2012年

2 任建峰;張玉忠;孫國;;一種新的柔性車間排序問題[A];中國企業(yè)運籌學學術交流大會論文集[C];2005年

相關博士學位論文 前1條

1 陳仕平;若干組合優(yōu)化問題的近似算法設計與分析[D];浙江大學;2002年

相關碩士學位論文 前10條

1 王敏;基于圖特征的介度中心近似算法研究[D];曲阜師范大學;2015年

2 張亞平;最小賦權連通k-子圖覆蓋問題的近似算法[D];新疆大學;2015年

3 張永俊;廣義非線性分式規(guī)劃問題的近似算法[D];河南師范大學;2015年

4 朱婷婷;具有不同釋放時間的單機重新排序問題的近似算法[D];蘭州大學;2016年

5 王克紅;均勻限制NP-完備間題及其近似算法設計[D];云南大學;2016年

6 申子慧;廣義多乘積規(guī)劃問題的近似算法[D];河南師范大學;2016年

7 劉冰冰;POMDP近似算法的研究與設計[D];中國科學技術大學;2017年

8 李彥杰;連通控制吸收集的近似算法[D];新疆大學;2013年

9 劉海;非光滑問題的三次近似算法[D];北京工業(yè)大學;2014年

10 張諸俊;異構車輛路徑問題近似算法的研究[D];華東師范大學;2014年

，

本文編號：2339918