工件权重带限制的最小化最大加权完工时间的单机在线排序问题

本文考虑了最小化最大加权完工时间的单机在线排序问题,要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性,即apj≤wj≤bpj(a≥(5√−1)/2b,b≥a)且若wi>wj则pi≥pj,如果wi=wj则pi=pj。工件以时间在线的方式到达,只有工件Jj在达到释放时间rj后,决策者才知晓工件的基本信息,如加工时间pj和权重wj。对于此问题,首先利用对手法证明了其下界为1+b/(b+a),随后给出了竞争比为1+b/(b+a)的最好可能的在线算法。特别地,当a=(5√−1)/2b时,该算法的竞争比为(5√+1)/2。

带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用(设施的开设费用与连接费用之和),也会影响到对其他顾客的服务质量。研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题。该问题是无容量设施选址问题的推广。问题可描述如下:给定设施集合、顾客集,以及设施开设费用和顾客连接费用,目标是选择设施的子集开设以满足顾客的需求,使得设施开设费用与连接费用之和最小。利用原始对偶技巧设计了近似算法,证明了该算法的近似比是9。

碳交易环境下政府循环率规制对生产者尽规模式的影响机理

绿色发展要求生产者承担节能减排和回收、循环并再利用的责任。碳限额交易政策既约束生产者的行为又诱导生产者生产方式的转变。循环率规制政策赋予生产者对废旧电子电器设备(WEEE)循环利用的责任。基于碳交易环境,文章首先研究循环率规制约束下生产者尽规模式的选择,然后探究面对愈加严格的法律法规,生产者实现尽规的方式,最后分析政府制定的循环率目标对社会福利的影响。研究结果表明,生产者有三种尽规模式可选择,并得到其阈值;面对不断严格的规制要求,生产者可以通过增加再制造品的产量、减少减排投资和新产品产量的方式实现尽规;研究还发现随着政府规制要求的提高,生产者利润减少,但这并不意味着消费者剩余一定减少,并且环境影响随着循环率目标的提高有可能反而增大,即并非循环率目标越高对环境越有利。