带有不可用区间的可拒绝排序问题

发布时间：2019-10-13 19:22

【摘要】：在现实生产中,加工工件在排序中越晚开始加工,它的实际加工时间就会越大。比如金融管理、钢铁生产、消防、资源分配和国防等等,任何延迟都会导致退化现象的产生。同时,工件在加工之前一般需要预加工的过程,预加工所用的时间就称为释放时间。而且,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,该时间段即为机器的不可用区间。经典的排序问题一般假设所有的工件都进行加工,对于工件可拒绝的排序问题,厂家通常会拒绝一些获利相对较小的工件,拒绝工件虽然可以节约生产成本,但是需要付出一定的惩罚费用,该惩罚费用即为拒绝惩罚。比如航空业、电子工业等等。本文研究带有释放时间、退化效应、拒绝工件及不可用区间的排序问题。该问题中,所有工件的释放时间是相同的。工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。机器带有一个不可用区间,在这段时间内,机器无法工作。具体内容概括如下:1.讨论了目标函数是所有加工工件的最大完工时间与所有拒绝工件的拒绝惩罚之和的单机排序问题。首先给出了拟多项式时间的动态规划算法,最后得到了全多项式近似方案,并分析了该近似方案的时间复杂性。2.讨论了目标函数是所有加工工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和的单机排序问题。首先,说明了这个问题是一般意义NP-难的,然后通过划分程序的方法得到了全多项式近似方案,最后,分析了该近似方案的时间复杂性。3.讨论了两台机器排序问题。其中一台机器带有一个不可用区间,在这段时间内,机器无法工作,另外一台机器一直可用。讨论的目标函数所有加工工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先,说明了这个问题是一般意义NP-难的,然后通过划分程序的方法得到了全多项式近似方案,最后,分析了该近似方案的时间复杂性。
【学位授予单位】：沈阳师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223

【相似文献】

相关期刊论文 前10条

1 周泓,张惠民;求解多目标作业排序问题的遗传算法[J];系统工程理论与实践;2001年08期

2 周泓,姬彬;求解作业排序问题的通用混合遗传算法研究[J];系统工程理论与实践;2001年12期

3 陈德伍,张 峰;一类新的可控排序问题(英文)[J];运筹学学报;2001年04期

4 张瑞,刘国珍;单机排序问题最优解方法[J];聊城师院学报(自然科学版);2001年02期

5 黎群;单台机器多目标作业排序问题的探讨[J];系统工程理论方法应用;2001年02期

6 方保昒,徐汉忠;用单亲遗传算法解具有窗口式交货期的多机加工排序问题[J];系统工程理论方法应用;2001年04期

7 宋政芳,孙世杰,吴春燕;一个超前有奖迟后受罚的排序问题(英文)[J];运筹学学报;2002年04期

8 赵传立,唐恒永;具有相关调整时间的排序问题[J];沈阳师范学院学报(自然科学版);2002年01期

9 郑自途;关于"三台以上机床作业排序问题"的算法[J];天津理工学院学报;2002年04期

10 张玉忠,苗翠霞;复制法及其在分批排序问题中的应用[J];曲阜师范大学学报(自然科学版);2004年02期

相关会议论文 前10条

1 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

2 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 谭万达;;二元对比排序中的最少逆序原理[A];中国系统工程学会模糊数学与模糊系统委员会第五届年会论文选集[C];1990年

8 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 陈荣军;唐国春;;自由作业环境下的供应链排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

相关重要报纸文章 前1条

1 山东 赵玉勇;数组，你的规律机器[N];电脑报;2004年

相关博士学位论文 前10条

1 仲维亚;供应链管理中的若干排序问题研究[D];浙江大学;2008年

2 尹晓;基因组重组排序问题的算法研究[D];山东大学;2010年

3 余炜;若干网络排序问题的算法和复杂性研究[D];华东理工大学;2010年

4 张安;带服务等级的在线排序问题及相关问题研究[D];浙江大学;2009年

5 郑睿;钢铁生产中的批处理机作业排序问题算法研究[D];复旦大学;2009年

6 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

7 李好好;若干排序问题研究[D];浙江大学;2014年

8 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

9 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

10 王成飞;几类新型在线分批排序问题[D];曲阜师范大学;2011年

相关硕士学位论文 前10条

1 董柳毅;与误工有关的多目标排序问题[D];重庆师范大学;2009年

2 王迅娣;成组加工排序和供应链在线排序问题[D];曲阜师范大学;2010年

3 王洁明;有关代理竞争排序问题的研究[D];华东理工大学;2011年

4 刘丽丽;分批排序问题[D];曲阜师范大学;2000年

5 鄢楚楠;2，，4-逆序变换的置换排序问题[D];浙江大学;2006年

6 张兵权;单位加工时间的公共时间窗单机分组排序问题[D];浙江大学;2006年

7 姜冠成;分批排序问题和资源约束排序问题[D];苏州大学;2005年

8 胡荣;一类分装式排序问题的计算方法和计算复杂性研究[D];武汉科技大学;2006年

9 马蕾;带传递时间的通信模型中的树约束排序问题[D];兰州大学;2007年

10 王小明;不允许等待的混合流水两车间排序问题[D];清华大学;2002年

本文编号：2548848