平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

单机排序问题1|rj,prmp|∑wj(1-e-acj)的动态在线调度

本文首先一般化了可中断的概念,并建立了相应的中断-安装重复模型,然后研究了单机排序问题1 |rj,prmp|∑wj(1-c-acj)在中断-重复和中断-安装重复模型下的动态在线排序问题,给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则.     

判断矩阵的广义一致性变换及其排序的一种算法

针对不同标度构造的判断矩阵的一致性检验以及排序问题,给出了判断矩阵广义一致性变换的定义,并论证了判断矩阵经广义一致性变换后所具有的性质.通过对比分析指出本文的研究结论具有更广的应用范围,深化了对参数β的理解,给出了该参数取值范围的一个合理区间.最后,归纳出由不同标度构造的判断矩阵具体的广义一致性变换及其排序方法.     

基于端点白化权函数聚类的水环境质量等级评价分析

为更准确地评价水环境质量,将端点三角白化权函数灰色评估引入到水质综合评价中.针对以往灰色白化权函数评估主要通过测定指标灰聚类系数判定被评价对象的优劣强弱等级进行等级识别评价,对三角白化权函数计算方法进一步扩展,完成多评价对象的准确等级定位及比较排序.将这种方法应用于山东省聊城市东昌湖水水质评价中,经实例计算证明基于三角白化权函数灰色评估评价模型的稳定性、合理性和实用性为水质评价研究方法提供了新的思路和借鉴.     

改进种群多样性的双变异差分进化算法

差分进化算法(DE)是一种基于种群的启发式随机搜索技术,对于解决连续性优化问题具有较强的鲁棒性.然而传统差分进化算法存在种群多样性和收敛速度之间的矛盾,一种改进种群多样性的双变异差分进化算法(DADE),通过引入BFS-best机制(基于排序的可行解选取递减策略)改进变异算子"DE/current-to-best",将其与DE/rand/1构成双变异策略来改善DE算法中种群多样性减少的问题.同时,每个个体的控制参数基于排序自适应更新.最后,利用多个CEC2013标准测试函数对改进算法进行测试,实验结果表明,改进后的算法能有效改善种群多样性,较好地提高了算法的全局收敛能力和收敛速度.     

在成组技术下带恶化和学习效应的单机排序问题

本文研究了带依靠时间的恶化效应和依靠位置的学习效应的成组排序问题。模型中,组安装时间是开始安装时间的线性函数,工件的加工时间带恶化和学习效应,目标函数分别为最小化时间表长问题和最小化总完工时间问题。基于对问题的分析,给出了多项式算法。     

具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。     

基于网络客户评论的产品口碑排序方法

电子商务时代,产品的网络口碑已成为消费者做购买决策的重要参考依据。本文利用客户评论信息,依据产品的评分及产品之间的对比投票数据,提出了一个新的产品口碑排序方法。首先利用产品两两间的对比投票计算各自的相对口碑,再采用贝叶斯平均方法修正原始客户评分,然后将二者结合得到产品的总口碑,进而对产品的网络口碑进行排序。实验数据采自第三方点评网站中的产品对比投票数据,实验结果表明本文提出的产品口碑排序方法具有较高的支持度,且与产品销量排序的相关性也很高。     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+\Delta（t）]$内到达工件的信息,这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长,其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。