同速度的具有m台通用机的n组工件的排序问题

 改进了经典的LPT(Longest Processing Time)算法，利用“首先空闲”准则安排机器，而对于工件的安排则按照“长时间任务优先”的原则，讨论了将n组工件安排在n台速度相同的专用机，m台同速度的通用机上的优化排序问题，得到了利用该近似算法所得的解T与最优解T*的一个估计：T/T*≤(2m+1)/(m+1)。     

具有通用机的四组工件排序问题

为解决实践中对多组任务的优化排序问题，文中提出了一种改进的最长工作优先安排（LPT）的算法，利用“最大相对加工时间”准则和“首先空闲”准则，讨论了将四组工件安排在四台速度相同的专用机、一台同速度的通用机上的Gmax问题，得到了利用该近似算法所得的解丁与最优解T^＊的一个估计：T/T^＊≤5/4，结果表明，采用该近似算法对工件排序，在最差情况下要比最优排序多出1/4的时间。     

有限制条件的单台机器的排序问题

根据给定n个工件在一台机器上加工时工件间的先后关系 ,定义了一个n个顶点的有向图D ,简化图D得排序图D ,通过穷举图D 的顶点的拓扑序列 ,搜索出了n个工件完工时间之和最小、机器加工完n个工件总时间最少和延误损失最少的加工顺序 .     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

误工排序问题的研究

误工排序问题是经典排序论中最基本和最重要的问题.40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现.本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义.这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果.     

具有共同松弛时间的恶化型工件排序问题研究

研究工件加工时间具有恶化效应的单机松弛工期排序问题.其中恶化效应指的是工件的实际加工时间是其开工时间的递增函数且所有工件的恶化率相同,工件的松弛工期等于其实际加工时间加上共同的松弛时间.目标是确定工件的一个排序和工件工期的共同松弛时间使得工件的提前时间、延迟时间和工期的共同松弛时间的线性加权和达到最小.用运筹学方法证明了该问题可以转化为两个向量的乘积问题,从而多项式时间可解,并给出了求解的最优算法.     

最大化接收工件总权值的批处理机在线排序

研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p0,一个到达时间r_j≥0,一个权值w_j0,一个必须交货期d_j0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).     

工件有工期并且可拒绝单机最小化最大提前时间的排序问题

研究工件有工期并且可拒绝的单机最小化最大提前时间的排序问题.若工件被拒绝,则需支付一定的惩罚费用;若工件被接受,则将该工件安排在机器上加工.目标函数是最小化被接收工件的最大提前完工时间与被拒绝工件的惩罚费用之和.通过对该排序问题的Pareto最优点的分析,得到该问题的多项式算法.     

极小化加权总完工时间的工件可拒绝排序 (运筹学与控制论)

经典的排序问题要求工件都必须进行加工,然而在实际中有时候由于一些特殊的原因可以考虑工件不加工。例如,加工时间非常大,或加工所需费用非常高,于是就不加工这一工件,而是通过支付一定的费用后送到外边"外加工"或购买更合算,这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝,并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中,目标函数是有限的总惩罚费用(总惩罚费用约束下)极小化加权总完工时间,工件到达时间都相同的同型机问题,设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法。     

具有固定顺序的重新排序问题

在生产实际中经常会出现顾客订单不同时到达的情况,为了保证先来顾客的需求和工件本身的要求,往往是先安排好的工件保持相对顺序不变,使其与后来顾客的工件重新排序.本文着重研究了这种使先来顾客的工件保持相对固定顺序,在有限错位限制的条件下使总目标函数值最优的重新排序问题。     

关于整正则有向图的补图与联图

把补图与联图这两种二元运算应用于正则有向图,发现无向正则图中的一些定理在有向图中亦成立,使定理的应用范围更加宽广,在此基础上进一步探讨了其成为整谱图的条件,从而得到了构造整谱有向图的新方法,可以用来构造新的整谱有向图.     

利用有向图的强连通性判断方阵的不可约性

给出了利用有向图的强连通性来判断方阵的不可约性的相关结论,并给出了相应的算法。     

用Tensor乘积法构造整谱有向图

通过研究Tensor乘积图与其谱之间的关系,得到Tensor乘积图是整谱图的条件,并由此获得了构造新的整谱图的方法,找到了一些新的整谱有向图.     

一类特殊的双色有向图的本原性

文章研究了只有两个圈C1,C2的双色有向图,给出了这类双色有向图本原的充分必要条件.     

具有第3大Wiener指数的有向图

通过有向图的Wiener指数,可以给有向网络的平均距离和节点的中介中心性赋有限的值,进而应用于大规模网络的分析.在所有n阶有向图中,有向圈C^→_n能取到极大Wiener指数,C^→+_n能取到第2大Wiener指数,利用反证法及分类讨论法对有向图的Wiener指数进行研究,得出了具有第3大Wiener指数的有向图,并刻画了相应的极图.     

有负权时有向图全路径算法研究

有向图有负权路径求解问题比较常见,但求所有可达路径的算法却见之甚少。本文在以前提出的一种有向图无负权所有可达路径搜索算法的基础上,提出一种先将有负权问题转换成无负权问题,进而用无负权算法求解之的方法。     

阶为23p群的Cayley图

为了反映Cayley图结构的规律性和自身特点,采取几类定义关系较复杂的有限群的Cayley有向图作法。结果表明:连接法只用定义关系中表示闭道路的字来表述,对于反映Cayley图结构的规律性和自身特点尚显不够。用几类定义关系较复杂的有限群Cayley有向图作法,不但揭示了Cayley图结构的规律性和自身特点,而且进一步解决了阶为23p群等一批有限群的Cayley有向图作法。该结果更简捷地完成Cayley有向图的几何实现。     

一种基于有向超图的规则库冗余及环路检测方法

当规则库的规模随着知识的更新而不断增大,规则库的维护就变得日益重要.其中,规则库的冗余和环路是影响规则库效率的重要问题.针对含有复合规则的产生式规则库,提出了一种基于有向超图的规则库表达方法,定义了其邻接矩阵和可达矩阵并推导出可达矩阵的计算方法.在此基础上给出了基于可达矩阵的冗余和环路检测算法.与已有的基于有向超图的算法相比,新算法图更简洁,矩阵规模更小,从而检测效率得到提高.实例证明该算法是有效可行的.     

一类本原双色有向图

研究了只有两个圈C1,C2的双色有向图.证明了这类双色有向图本原的充分必要条件,并给出了C2的顶点数为2时它的本原指数的下界.     

Distributed Nash equilibrium seeking design for energy consumption games of HVAC systems over digraphs

The energy consumption problem of heating, ventilation, and air conditioning systems over general directed graphs is investigated. The considered problem is firstly reformulated as a Nash equilibrium seeking problem, and a distributed consensus-based algorithm is then proposed to solve it. To address the challenge arising from general directed graphs, a distributed estimation algorithm is embedded such that the explicit dependence on the left eigenvector associated with the eigenvalue zero of the Laplacian matrix can be avoided. Then, the exponential convergence of the proposed distributed Nash equilibrium seeking algorithm is established under a standing assumption. A numerical example is finally provided to verify the effectiveness of the proposed algorithm.