【摘要】：研究工件既可以在制造商的同類(lèi)機(jī)上加工,又可以一定費(fèi)用分包給某承包商加工的排序決策問(wèn)題·假設(shè)制造商有若干承包商,每個(gè)承包商有足夠多機(jī)器用于加工工件·制造商需要確定被分包的工件集,以及未分包工件的加工順序,使得工件最大完工時(shí)間與加工、分包費(fèi)用線(xiàn)性和最小.證明問(wèn)題的NP困難性,用數(shù)學(xué)規(guī)劃及組合方法設(shè)計(jì)了問(wèn)題的近似算法,并分析算法性能比與漸近性.
[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.
【作者單位】： 常州工學(xué)院數(shù)學(xué)系;上海第二工業(yè)大學(xué)管理工程研究所;
【基金】：國(guó)家自然科學(xué)基金(71371120)資助項(xiàng)目
【分類(lèi)號(hào)】：O223

【相似文獻(xiàn)】

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

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

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

3 馬紹漢;一類(lèi)限制樹(shù)問(wèn)題的復(fù)雜性及其近似算法[J];山東大學(xué)學(xué)報(bào)(自然科學(xué)版);1984年01期

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

5 杜林古;;帶風(fēng)向投遞員問(wèn)題的一個(gè)多項(xiàng)式1—近似算法[J];山東紡織工學(xué)院學(xué)報(bào);1992年01期

6 何勇;帶核集分劃問(wèn)題的一個(gè)線(xiàn)性(1/7)-近似算法[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);1997年04期

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

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

9 李亮,葉尚輝;工程結(jié)構(gòu)可靠性分析中高維概率積分的一種近似算法[J];應(yīng)用力學(xué)學(xué)報(bào);1989年02期

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

相關(guān)會(huì)議論文 前2條

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

2 任建峰;張玉忠;孫國(guó);;一種新的柔性車(chē)間排序問(wèn)題[A];中國(guó)企業(yè)運(yùn)籌學(xué)學(xué)術(shù)交流大會(huì)論文集[C];2005年

相關(guān)博士學(xué)位論文 前1條

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

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

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

2 張亞平;最小賦權(quán)連通k-子圖覆蓋問(wèn)題的近似算法[D];新疆大學(xué);2015年

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

4 朱婷婷;具有不同釋放時(shí)間的單機(jī)重新排序問(wèn)題的近似算法[D];蘭州大學(xué);2016年

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

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

7 劉冰冰;POMDP近似算法的研究與設(shè)計(jì)[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

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

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

10 張諸俊;異構(gòu)車(chē)輛路徑問(wèn)題近似算法的研究[D];華東師范大學(xué);2014年

，

本文編號(hào)：2339918