|
|
|
| 拒绝可缓冲的2台同类机半在线排序问题的近似算法 |
|
| Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer |
|
|
|
摘要 研究了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的参数竞争比.
|
|
|
收稿日期: 2013-05-13
|
| [1] |
任燕芝. 基于动态分级和邻域反向学习的改进粒子群算法[J]. 浙江大学学报（理学版）, 2018, 45(3): 261-271. |
| [2] |
韩萌. 耗散结构和差分变异混合的鸡群算法[J]. 浙江大学学报（理学版）, 2018, 45(3): 272-283. |
| [3] |
王峰, 刘三阳. 无穷多目标优化的Geoffrion真有效性及其在鲁棒优化中的应用[J]. 浙江大学学报（理学版）, 2018, 45(3): 294-297,313. |
| [4] |
张倩倩, 郭锂. 模的有限表现系统和Lazard引理[J]. 浙江大学学报（理学版）, 2018, 45(3): 298-303. |
| [5] |
张晓建. 二阶Emden-Fowler型变时滞中立型微分方程的振荡性[J]. 浙江大学学报（理学版）, 2018, 45(3): 308-313. |
| [6] |
徐华, 钱程. 修正Durrmeyer型Bernstein-Stancu算子的逼近[J]. 浙江大学学报（理学版）, 2018, 45(3): 314-319. |
| [7] |
汪建妹, 杨华, 曾银欢, 吴俐勤, 李锐, 袁玉伟, 钱鸣蓉. 超高效液相色谱-串联质谱法测定蜂蜜中抗生素和农药浓度[J]. 浙江大学学报（理学版）, 2018, 45(3): 330-342. |
| [8] |
陈有利, 徐慧燕, 卢美, 朱业, 刘瑞. 用调整边界层湍流系数的QNSE方案模拟夏秋季沿海大风的应用研究[J]. 浙江大学学报（理学版）, 2018, 45(3): 343-350,362. |
| [9] |
芦佳玉, 延军平, 李英杰. 基于SPEI及游程理论的云贵地区1960—2014年干旱时空变化特征[J]. 浙江大学学报（理学版）, 2018, 45(3): 363-372. |
| [10] |
吴宝清, 吴晋峰, 周芳如, 杨春华. 旅游目的地形象清晰度及测评方法——以西安为例[J]. 浙江大学学报（理学版）, 2018, 45(3): 379-390. |
| [11] |
林建伟. 在美国破产保护法第十一章下公司债券的定价和最佳破产边界研究[J]. 浙江大学学报（理学版）, 2018, 45(3): 320-329. |
| [12] |
马小雯, 章笑艺, 来丽芳, 张丰, 杜震洪, 刘仁义. 基于地理探测器的浙江省空气质量风险因子分析[J]. 浙江大学学报（理学版）, 2018, 45(3): 351-362. |
| [13] |
饶传坤, 韩烨子. 新型城镇化背景下工业型城镇空间规划引导初探——以慈溪市观海卫镇为例[J]. 浙江大学学报（理学版）, 2018, 45(3): 373-378. |
| [14] |
郭立婷. 基于自适应和变游走方向的改进狼群算法[J]. 浙江大学学报（理学版）, 2018, 45(3): 284-293. |
| [15] |
孟令胜. 酉不变范数下{1,3}-和{1,4}-逆的扰动界[J]. 浙江大学学报（理学版）, 2018, 45(3): 304-307. |
|
|
|
|
2014, Vol. 41 
