• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文期刊> 《浙江大学学报（理学版）》 >拒绝可缓冲的2台同类机半在线排序问题的近似算法

拒绝可缓冲的2台同类机半在线排序问题的近似算法

         
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

研究了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的参数竞争比.

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号