带拒绝和到达时间的排序问题
本文选题：排序 + 拒绝费用 ； 参考：《华东理工大学》2017年硕士论文
【摘要】：在经典排序问题中,所有的工件都必需被接受且加工。然而,在很多实际生产情况下,特别是有大批量订单时,接受加工所有的订单可能会导致订单的延误,由此会带来高昂的存贮和延误费用。因此,一些工厂可能会把部分订单外包或者拒绝。带拒绝的排序问题无论是实践方面还是理论方面都非常有意义,所以在过去十几年中吸引大量研究者的关注。在本课题中,首先考虑这样一个带有拒绝工件的单机排序问题。有n个工件,每个工件都有一个确定的到达时间,加工时间和拒绝费用。接受加工一部分工件并且对这些工件进行排序。这个问题是一般NP-困难的。本文为这个问题建立一个混合整数规划模型,并设计了一个分支定界的算法。然后给出了一个1.618-近似算法。通过数值模拟实验,来观测分支定界算法的效果。同时,也给出了近似算法的模拟结果。随后,将这个问题推广到平行机上,并给出了一个2-近似算法,同样通过模拟实验来检验这个算法的有效性。
[Abstract]:In classical sorting problems, all jobs must be accepted and processed. However, in many actual production situations, especially when there is a large number of orders, accepting all orders may lead to the delay of orders, which will bring high storage and delay costs. As a result, some factories may outsource or reject some orders. The problem of ordering with rejection is of great significance both in practice and in theory, so it has attracted the attention of a large number of researchers in the past decade. In this paper, we first consider such a single machine scheduling problem with rejected jobs. There are n jobs, each with a definite arrival time, processing time and rejection cost. Accept the processing of parts of the work and sort them. This problem is generally NP- difficult. In this paper, we establish a mixed integer programming model for this problem and design a branch and bound algorithm. Then a 1.618-approximate algorithm is given. The effect of branch and bound algorithm is observed by numerical simulation experiment. At the same time, the simulation results of the approximate algorithm are given. Then, the problem is extended to parallel machines, and a 2-approximation algorithm is given. The validity of the algorithm is also tested by simulation experiments.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223
【相似文献】
相关期刊论文 前10条
1 姜振多;孙世杰;吴志刚;;排序问题的稳定性分析(英文)[J];Journal of Shanghai University(English Edition);2008年01期
2 谭素平;;排序问题的分类与特点[J];科技信息;2012年36期
3 越民义,韩继业;排序问题中的一些数学问题[J];数学的实践与认识;1976年03期
4 越民义,韩继业;同顺序m×n排序问题的一个新方法[J];科学通报;1979年18期
5 吴家强;用分段选优法求解“排序问题”[J];武汉水利电力学院学报;1979年03期
6 戴志勇;;一类排序问题最优工序定义的等价性[J];武汉钢铁学院学报;1979年02期
7 韩继业;排序问题的一个判别条件和一类特殊的m×n排序问题[J];应用数学学报;1980年04期
8 吴在德;梁学信;;排序问题计算加工时间的一种方法及其一个应用[J];华侨大学学报;1981年01期
9 叶懋冬;;关于过竿问题与多台机床上零件加工的排序问题(Ⅰ)[J];浙江大学学报;1982年04期
10 徐本顺;有提前和延误损失的一类排序问题[J];华中工学院学报;1983年04期
相关会议论文 前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年
相关博士学位论文 前10条
1 高强;一些现代排序问题的算法设计与分析[D];华东理工大学;2015年
2 谷存昌;工件的加工和配送协作排序问题[D];曲阜师范大学;2015年
3 殷娜;依赖于资源分配的排序问题研究[D];上海大学;2015年
4 仲维亚;供应链管理中的若干排序问题研究[D];浙江大学;2008年
5 尹晓;基因组重组排序问题的算法研究[D];山东大学;2010年
6 余炜;若干网络排序问题的算法和复杂性研究[D];华东理工大学;2010年
7 张安;带服务等级的在线排序问题及相关问题研究[D];浙江大学;2009年
8 郑睿;钢铁生产中的批处理机作业排序问题算法研究[D];复旦大学;2009年
9 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年
10 李好好;若干排序问题研究[D];浙江大学;2014年
相关硕士学位论文 前10条
1 李韦萱;两类带有维修的排序问题[D];沈阳师范大学;2015年
2 周雨波;与工件释放时间和交货时间有关的排序问题及近似算法[D];兰州大学;2015年
3 张龙;优化交货期窗口的单机供应链排序问题[D];曲阜师范大学;2015年
4 于萌萌;工件带有恶化效应的博弈排序问题[D];曲阜师范大学;2015年
5 李雨洁;恒速机下的有限资源博弈排序最优性研究[D];曲阜师范大学;2015年
6 尚明明;带有GDD假设的几类重新排序问题研究[D];郑州大学;2015年
7 黄保斌;分批的供应、加工、配送供应链排序问题[D];曲阜师范大学;2015年
8 苏晓彤;机器具有维护时段的带运输排序问题研究[D];浙江理工大学;2016年
9 杨佳雯;两阶段车间作业排序问题的研究[D];浙江理工大学;2016年
10 苗利辉;并行分批在线排序问题和排序博弈问题的研究[D];中国海洋大学;2015年
，本文编号：1934257
本文链接：https://www.wllwen.com/kejilunwen/yysx/1934257.html
