【近似算法的设计与分析】拒绝可缓冲的2台同类机半在线排序问题

本文作者：闵啸；刘静；朱俊蕾；姜明；成功正常投稿发表论文到《浙江大学学报(理学版)》2014年04期,引用请注明来源400期刊网！

【摘要】：研究了2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2,速度分别为1和s∈[1,+∞),加工不允许中断,工件Jj按照列表在线到达,每个工件带有2个参数:加工长度tj、拒绝罚值pj(模型1中)或拒绝获益pj(模型2中),当工件到达时,可以被接受并分给某台机器加工,也可以被拒绝,需付出一定的罚值(模型1)或取得一定的收益(模型2),目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和;第2个模型中要求极大化机器最小负荷和总收益之和.此外,在接受或拒绝的决策环节上提供一个缓冲区B,其容量为k≥1,任一时刻至多可以存放k个工件,当工件到达时,若缓冲区未饱和,则可暂时存入B;若已饱和,则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策.本模型所研究的是经典可拒绝模型中的一个松弛问题,属半在线可拒绝模型.最后针对以上2个模型,分别给出了s在区间[1,+∞)上的近似算法,并证明了各自关于s的参数竞争比.
【论文正文预览】：可拒绝平行机排序问题有较强的实际应用背景.如某个生产者在考虑其利益的基础上可以对任务做选择,若接受一项任务,则需消耗一定的加工成本,或将其拒绝,则要接受相应的惩罚;或者拒绝后反而获得一定的收益.本文考虑2台可拒绝同类机的排序问题,设有2台同类机M1,M2,加工速度经规范
【文章分类号】：O223
【稿件关键词】：同类机半在线可拒绝排序缓冲区竞争比
【参考文献】:

• JIANG Yi-wei;HU Jue-liang;WENG Ze-wei;ZHU Yu-qing;;Parallel machine covering with limited number of preemptions[J];Applied Mathematics:A Journal of Chinese Universities(Series B);2014年01期
• 吴用;黄宜坤;杨启帆;;已知工件最大加工时间的平行机排序问题[J];浙江大学学报(理学版);2008年01期
• 闵啸;刘静;;l_2范数下两台带缓冲区同型机半在线排序问题的最优算法[J];浙江大学学报(理学版);2008年05期
• 闵啸;刘静;王玉青;;两台可中断同类机可拒绝半在线排序问题的近似算法[J];浙江大学学报(理学版);2010年05期
• 唐国春;;2003年到2005年排序(调度)学科在中国的发展(I)[J];上海第二工业大学学报;2006年03期
• 张峰;;具有就绪时间与先后约束的工件可拒绝排序[J];上海第二工业大学学报;2009年01期
• 吴用;杨启帆;;预知工件大小上界的平行机排序问题[J];系统科学与数学;2010年04期
• 闵啸;;带复合信息的三台平行机半在线排序问题(英文)[J];运筹学学报;2006年01期
• 闵啸,耕田;带缓冲区的平行机半在线排序问题的近似算法[J];嘉兴学院学报;2005年03期
• 闵啸;沈奕;;三台带服务等级的可拒绝同型机在线排序问题[J];嘉兴学院学报;2013年06期
• 侯丽英;具有服务等级的在线和半在线排序及其相关问题[D];上海大学;2011年
• 吴用;预知复合信息半在线排序问题算法研究[D];浙江大学;2009年
• 李世胜;基于运行时的程序执行模型研究[D];中国科学技术大学;2010年
• 顾满占;若干随机排序问题的算法研究[D];华东理工大学;2010年
• 刘想德;作业车间实时调度若干关键问题研究[D];重庆大学;2013年
• 陶继平;基于实例空间压缩的在线及半在线调度算法的竞争分析[D];上海交通大学;2014年
• 吴用;平行机覆盖问题的半在线算法研究[D];浙江大学;2006年
• 周昊;（半）在线排序中若干问题的研究[D];浙江大学;2005年
• 陈强;工件具有相似长度的半在线排序问题[D];湖南师范大学;2009年
• 杨丽英;工件有到达时间排序问题的LS算法分析[D];湖南师范大学;2009年
• 成夏炎;关于在线排序的近似算法的若干研究[D];湖南师范大学;2010年
• 武光华;可拒绝排序和两台同类机半在线排序问题[D];曲阜师范大学;2010年
• 刘卯;Ip范数下两台同类机在线排序问题的若干研究[D];北京邮电大学;2013年
• 翁则威;可中断次数受限的平行机排序问题研究[D];浙江理工大学;2013年
• 霍志明;工件可转包加工的排序问题研究[D];上海大学;2013年
• 姚川;两台同类机半在线订单排序问题下界和近似算法[D];华东理工大学;2014年
• 朱赋;同顺序流水作业排序问题的一个启发式算法[J];应用数学与计算数学学报;2000年02期
• 时凌;工件带到达时间和服务器的平行机排序问题复杂性和启发式算法[J];湖北民族学院学报(自然科学版);2004年03期
• 时凌;转盘上的Flow-shop排序问题的复杂性[J];武汉科技学院学报;2004年08期
• 李立亚;;Q_2,r_j |sum| C_(min)问题的半在线排序[J];湖北教育学院学报;2007年08期
• 李立亚;;Q_2,r_j |sum| C_(min)问题的半在线排序[J];江西理工大学学报;2007年06期
• 田乐;赵传立;;极小化总完工时间的同时加工排序[J];数学的实践与认识;2009年20期
• 唐春明;石桂花;姚正安;;排序问题的安全多方计算协议[J];中国科学:信息科学;2011年07期
• 戴志勇;;一类排序问题最优工序定义的等价性[J];武汉科技大学学报(自然科学版);1979年02期
• 向荣华;张守诚;马家騄;;同顺序m×n排序问题的一种近似解法[J];西北大学学报(哲学社会科学版);1982年01期
• 张鸣龙;加工时间为随机变量的排序问题[J];郑州航空工业管理学院学报;1989年01期
• 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年
• 张吉军;;基于可能度的区间数排序方法研究[A];第六届中国青年运筹与管理学者大会论文集[C];2004年
• 孔令启;岳金彩;郑世清;韩方煜;;列队竞争算法求解多目的厂间歇生产过程排序问题[A];第一届全国化学工程与生物化工年会论文摘要集(上)[C];2004年
• 浦明松;罗守山;刘文;;基于RSA的安全多方排序问题的研究[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年
• 贾春福;涂奉生;;带滞留时间的3—机器装配型Flowshop排序问题[A];1996中国控制与决策学术年会论文集[C];1996年
• 李东;杨丹;邓林;王时龙;;Qm‖C_(max)的一种启发式算法的性能分析[A];2005中国控制与决策学术年会论文集（下）[C];2005年
• 张峰;;具有先后约束关系的工件加工时间可控排序问题的线性规划松弛算法[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年
• 刘晓惠;;一类带安装时间的多客户竞争排序问题[A];第十一届中国青年信息与管理学者大会论文集[C];2009年
• 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年
• 靳志宏;马钦海;朴惠淑;关志民;;计划与排序问题的可逆性及其应用[A];2005中国控制与决策学术年会论文集（下）[C];2005年
• 米厚民;情牵“三农”问题[N];山西日报;2004年
• ;GreenBrowser奇赢技巧[N];中国电脑教育报;2005年
• 山东 赵玉勇;数组，你的规律机器[N];电脑报;2004年
• ;农村义务教育全免费：中国有财力承担[N];南方周末;2005年
• 流星;高考GPS系统应运而生[N];计算机世界;2006年
• 粱美娜;“环保风暴”：一场不该戛然而止的博弈[N];中国经营报;2005年
• 仪句;搜索引擎 收费时代的信号灯[N];网络世界;2002年
• 李兴文;国务院减负办将专项治理乱检查、乱评比、乱培训[N];中国企业报;2006年
• 毛建国;惠民政策就要不断做“加法”[N];农民日报;2008年
• 山东 赵玉勇;小博士编程[N];电脑报;2004年
• 王磊;面向订单生产的供应链排序问题研究[D];暨南大学;2011年
• 李好好;若干排序问题研究[D];浙江大学;2014年
• 余炜;若干网络排序问题的算法和复杂性研究[D];华东理工大学;2010年
• 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年
• 汪磊扬;一类带批运输的排序问题研究[D];华东理工大学;2012年
• 钟雪灵;带强制工期非正则目标函数的排序问题研究[D];暨南大学;2010年
• 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年
• 尹晓;基因组重组排序问题的算法研究[D];山东大学;2010年
• 杨名;若干流水作业排序问题的算法研究[D];华东理工大学;2011年
• 罗润梓;平行机半在线排序问题[D];上海大学;2005年
• 任建锋;两种新型排序问题的近似算法[D];曲阜师范大学;2003年
• 蔡圣义;平行同型机半在线排序问题的若干研究[D];浙江大学;2002年
• 马丽娜;平行机上工件有到达时间的在线和半在线排序问题[D];湖南师范大学;2010年
• 朱洪利;供应链管理中的分批调度问题[D];曲阜师范大学;2010年
• 梁喆敏;加工时间恶化的排序问题的讨论[D];浙江大学;2007年
• 牟启燕;带一个服务器的两台机器自由作业排序问题的近似算法[D];华东理工大学;2011年
• 吴用;平行机覆盖问题的半在线算法研究[D];浙江大学;2006年
• 王梦兰;混合式遗传算法及其在指派问题与排序问题中的应用[D];西南交通大学;2002年
• 孙叶平;误工排序问题[D];重庆师范大学;2008年
• 陈小林;误工排序问题最优性Pinedo证明的完善和发展[D];重庆师范大学;2009年

【稿件标题】：【近似算法的设计与分析】拒绝可缓冲的2台同类机半在线排序问题的近似算法
【作者单位】：嘉兴学院数理与信息工程学院;杭州电子科技大学软件与智能技术研究所;
【发表期刊期数】：《浙江大学学报(理学版)》2014年04期
【期刊简介】：0......更多浙江大学学报(理学版)杂志社(http://www.400qikan.com/qk/13807/)投稿信息
【版权所有人】：闵啸；刘静；朱俊蕾；姜明；

更多自然类论文详细信息: 【近似算法的设计与分析】拒绝可缓冲的2台同类机半在线排序问题 论文代写
http://m.400qikan.com/lw-23882 论文代发

相关专题：石油教育杂志社 内部控制