具有分包功能的同类机排序

发布时间：2018-11-18 11:28

【摘要】：研究工件既可以在制造商的同类机上加工,又可以一定费用分包给某承包商加工的排序决策问题·假设制造商有若干承包商,每个承包商有足够多机器用于加工工件·制造商需要确定被分包的工件集,以及未分包工件的加工顺序,使得工件最大完工时间与加工、分包费用线性和最小.证明问题的NP困难性,用数学规划及组合方法设计了问题的近似算法,并分析算法性能比与渐近性.
[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.
【作者单位】： 常州工学院数学系;上海第二工业大学管理工程研究所;
【基金】：国家自然科学基金(71371120)资助项目
【分类号】：O223

【相似文献】

相关期刊论文 前10条

1 魏麒;蒋义伟;;一类两阶段杂交流水作业的近似算法(英文)[J];软件学报;2012年05期

2 刘振宏;组合最优化问题的近似算法[J];数学的实践与认识;1983年03期

3 马绍汉;一类限制树问题的复杂性及其近似算法[J];山东大学学报(自然科学版);1984年01期

4 杨延龄,戚文发;关于最优备件问题的近似算法的研究[J];工程数学学报;1989年01期

5 杜林古;;带风向投递员问题的一个多项式1—近似算法[J];山东纺织工学院学报;1992年01期

6 何勇;带核集分划问题的一个线性(1/7)-近似算法[J];高校应用数学学报A辑(中文版);1997年04期

7 季敏,何勇;带核集分划问题的一个改进近似算法[J];系统工程理论与实践;2003年12期

8 何晓琼;陈冲;李荣珩;;工厂地址集中的k-种产品选址问题的近似算法[J];计算机工程与应用;2010年08期

9 李亮,叶尚辉;工程结构可靠性分析中高维概率积分的一种近似算法[J];应用力学学报;1989年02期

10 程建纲,秦成林;多处理机调度问题的一种近似算法[J];烟台大学学报(自然科学与工程版);1997年03期

相关会议论文 前2条

1 梁国宏;郭云霞;郑明发;;最大化下模函数的近似算法及其性能保证[A];第十届中国不确定系统年会、第十四届中国青年信息与管理学者大会论文集[C];2012年

2 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年

相关博士学位论文 前1条

1 陈仕平;若干组合优化问题的近似算法设计与分析[D];浙江大学;2002年

相关硕士学位论文 前10条

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

2 张亚平;最小赋权连通k-子图覆盖问题的近似算法[D];新疆大学;2015年

3 张永俊;广义非线性分式规划问题的近似算法[D];河南师范大学;2015年

4 朱婷婷;具有不同释放时间的单机重新排序问题的近似算法[D];兰州大学;2016年

5 王克红;均匀限制NP-完备间题及其近似算法设计[D];云南大学;2016年

6 申子慧;广义多乘积规划问题的近似算法[D];河南师范大学;2016年

7 刘冰冰;POMDP近似算法的研究与设计[D];中国科学技术大学;2017年

8 李彦杰;连通控制吸收集的近似算法[D];新疆大学;2013年

9 刘海;非光滑问题的三次近似算法[D];北京工业大学;2014年

10 张诸俊;异构车辆路径问题近似算法的研究[D];华东师范大学;2014年

，

本文编号：2339918