2025年,第29卷

    按期号、起始页码排序
    Please wait a minute...
    选择: 显示/隐藏图片
    1. 带有维护窗口的调度问题的综述
    袁园, 兰艳, 韩鑫
    运筹学学报(中英文)    2025, 29 (1): 1-18.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.001
    摘要110)   HTML0)    PDF(pc) (685KB)(63)    收藏

    近年来, 带有维护窗口的车间调度问题受到越来越多学者的广泛关注。现有文献中涉及到的维护窗口有四种类型: 固定维护窗口、滑动维护窗口、浮动维护窗口、速率可变的维护窗口。目前, 已有大量文献对这一问题进行研究, 但是还没有文献对这些结果进行总结。为了方便读者, 本文对带有维护窗口的调度问题已有的结果进行了总结, 简单地概述了在单台机、流水车间和开放车间环境下, 关于该类问题的复杂性结果、精确算法和近似算法。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    2. 具有学习效应的预制构件生产调度研究
    李娜, 马冉, 李龙, 张玉忠
    运筹学学报(中英文)    2025, 29 (1): 19-30.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.002
    摘要80)   HTML0)    PDF(pc) (656KB)(45)    收藏

    本文研究了预制构件生产环境下具有学习效应的单机调度问题, 建立以最小化最大加权完工时间为目标的调度模型。工件Jj的实际加工时长依赖于其开工时刻t, 模型为pj = bj(abt), 其中ab是非负参数, bj为工件Jj的基础加工时间。首先, 分析所研究模型的离线最优排序。其次, 研究该模型的在线调度问题, 其中工件以时间在线的方式到达, 提出一个竞争比为2 − bbmin的最好可能的在线算法, 其中bmin = min {bj|1 ≤ jn}。最后, 对模型进行数值模拟, 验证了该在线算法的有效性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    3. 基于松弛工期的总加权误工单机双代理排序问题
    崔同欣, 夏倩, 张新功
    运筹学学报(中英文)    2025, 29 (1): 31-40.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.003
    摘要70)   HTML1)    PDF(pc) (589KB)(20)    收藏

    本文研究了松弛工期下与总加权误工相关的单机双代理排序问题, 这里工件的松弛工期等于工件的加工时间加上某个松弛变量。涉及的两个模型分别为: 模型一是在第二个代理的误工工件个数不超过一个给定值的前提下, 使得第一个代理的总权误工最小; 模型二是在第二个代理的总完工时间不超过一个给定值的前提下, 使得第一个代理的总权误工最小。利用动态规划的方法对于两类问题分别给出了最优性质、拟多项式时间算法、以及时间复杂度分析, 并用算例实验来说明了算法的可行性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    4. 提高长尾数据知识图谱补全性能的一种新算法
    何苗惠, 段旭祥, 吴至友
    运筹学学报(中英文)    2025, 29 (1): 41-54.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.004
    摘要100)   HTML0)    PDF(pc) (781KB)(33)    收藏

    知识图谱是众多智能应用中一种重要的语义数据, 但其数据的不完备性给实际应用带来了很多困难, 因此需要对知识图谱中缺失的语义信息进行补全。知识图谱嵌入是知识图谱补全的重要方法之一, 这类方法通常在非长尾数据情况下具有较好的效果, 但在长尾数据情况下其效果较差。由于非长尾数据的语义较丰富, 为了提升长尾数据情况下知识图谱补全效果, 本文将非长尾数据作为监督知识迁移到长尾数据中, 提出了一种新的算法——融入期望最大化算法思想的双重嵌入方法, 来改进长尾数据的知识图谱补全性能, 进而提高其实际应用效果。通过在FB15K数据集中进行链接预测任务的对比实验, 实验结果表明本文提出的融入期望最大化算法思想的双重嵌入方法效果较好。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    5. 有两种故障状态的δ-冲击模型的检测及预防维修策略研究
    高俏俏, 岳德权
    运筹学学报(中英文)    2025, 29 (1): 55-62.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.005
    摘要76)   HTML0)    PDF(pc) (732KB)(18)    收藏

    本文研究了一类有两种故障状态的δ-冲击模型的预防维修策略, 系统是几何过程退化的, 并且在运行过程中系统故障可能有两种原因: 一种是由于自身寿命终止, 另一种是由于连续两次冲击的间隔小于某一固定值。系统的故障只有检测才可以发现, 当系统的工作时间达到某一值T时进行检测, 如未发生故障则进行预防维修, 预防维修使系统恢复到上一次故障维修后的状态, 如发生故障则进行故障维修, 且当系统的故障次数达到N时对其进行更换。以系统检测及预防维修的间隔和更换前的故障次数组成的二维策略(T, N)为策略, 利用更新过程和几何过程理论求出了系统长期运行单位时间内期望费用的表达式, 并进行了数值分析。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    6. 多准则敏感性的偏序分析方法
    岳立柱, 姚利微, 崔亚华, 许可
    运筹学学报(中英文)    2025, 29 (1): 63-76.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.006
    摘要81)   HTML0)    PDF(pc) (769KB)(28)    收藏

    多准则决策主要通过权重摄动构造敏感性分析方法, 当赋权困难或者发生争议时, 评价结果往往不够稳健。偏序敏感性分析以决策函数为目标函数、权重空间为约束条件建立规划问题, 借助极值点集构建方案间的偏序关系。最终应用Hasse图表达可能的变动结果, 得到方案和指标的敏感性程度。通过权重空间的变化, 偏序方法可以构造出适用于全局、局部和有限等多种敏感性分析方法。实例应用表明, 三类敏感性分析的偏序结果与仿真结果均完全一致, 体现了偏序方法的有效性和独特性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    7. 非合作情形下无领导者-跟随者顺序时的串联系统效率评价
    文瑶, 胡军华
    运筹学学报(中英文)    2025, 29 (1): 77-97.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.007
    摘要71)   HTML0)    PDF(pc) (1226KB)(38)    收藏

    非合作情形下, 用数据包络分析(data envelopment analysis, DEA)方法对串联系统进行效率评价的研究中, 经典的领导者-追随者网络DEA模型(或非合作网络DEA模型)可为系统及其子系统提供唯一的评价结果。但其前提是预先给定系统内部的领导者-追随者顺序。不同的顺序产生不同的评价结果, 且并非所有系统均在同一顺序中获得最佳效率。另外, 现有网络DEA研究多认为决策者是完全理性的, 与现实中决策者有限理性的表现不符。本文针对“非合作情形下无领导者-跟随者顺序时如何评价串联系统及其子系统效率”的问题, 基于字典式优化算法和前景理论, 提出新的串联系统效率评价方法。该方法可提供唯一的、全面的、可比较的效率评价结果。最后, 用14家电力公司数据验证该方法。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    8. 关于逆符号全控制数的上界
    尚华辉, 苗连英
    运筹学学报(中英文)    2025, 29 (1): 98-104.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.008
    摘要68)   HTML0)    PDF(pc) (455KB)(20)    收藏

    本文研究了图的逆符号全控制数的上界。通过分析并优化点集, 建立了度、奇点集、边数之间的关系, 得到了图的逆符号全控制数的5个上界, 并分别给出了相应的极图。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    9. 不确定参数下n人非合作博弈的逼近定理
    陈聪利, 杨辉, 杨光惠, 王春
    运筹学学报(中英文)    2025, 29 (1): 105-113.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.009
    摘要51)   HTML0)    PDF(pc) (616KB)(14)    收藏

    在已知不确定参数变化范围的前提下, 本文研究了不确定参数下n人非合作博弈的逼近定理。基于有限理性思想, 我们证明了不确定参数下n人非合作博弈的逼近定理, 为其NS平衡的求解算法提供了一个理论支撑。进一步, 我们通过一个具体算例验证了该结论的合理性。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    10. 一类考虑滑动摩擦力影响的追逃博弈问题
    侯敏, 于洋, 戴照鹏, 敬鲁晶, 高红伟
    运筹学学报(中英文)    2025, 29 (1): 114-126.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.010
    摘要75)   HTML1)    PDF(pc) (724KB)(16)    收藏

    本文以追逃博弈问题的经典模型之一——“homicidal chauffeur”博弈为基础, 考察汽车转弯时受滑动摩擦力影响的博弈问题的捕获区域。经典“homicidal chauffeur”博弈是基于足够粗糙的地面这一理想假设对汽车转弯时的速度进行处理的。然而在现实运动中, 地面粗糙程度不同会对转弯时汽车的速度造成不同的影响。本文建立模型对追逃过程中汽车速度给出全新的刻画, 求解最优策略, 分析与经典“homicidal chauffeur”博弈相比捕获区域的变化并阐述原因, 主要结论可用于陆地追逃、空战格斗等现实场景。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    11. 带随机工资的目标收益养老金计划的鲁棒最优投资和收益支付调整策略
    张欣茹, 马世霞, 张雨萌, 慕蕊
    运筹学学报(中英文)    2025, 29 (1): 127-141.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.011
    摘要72)   HTML0)    PDF(pc) (712KB)(33)    收藏

    本文在目标收益计划(TBPs)下考虑了具有违约风险和模型不确定性的最优投资和收益支付问题。养老金可以投资到无风险资产, 价格服从Heston模型的股票和违约债券。特别地, TBPs成员的工资是随机的。利用随机最优控制方法, 分别推导出了违约后和违约前的鲁棒最优策略和相应的值函数。此外, 还考虑了模糊中性情况下的最优策略。最后给出数值分析来说明参数对最优策略的影响, 从而为养老金管理者提供了有效的决策依据。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    12. 带机器维护的最小化总误工数期望的随机排序问题研究
    杜诗翩, 顾满占
    运筹学学报(中英文)    2025, 29 (1): 142-158.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.012
    摘要66)   HTML1)    PDF(pc) (707KB)(21)    收藏

    本文研究了一类带多次机器维护的单机随机排序问题, 其中所有工件有相同的加工时间和工期, 且工期为一个随机变量, 问题目标是确定工作间的数目及每个工作间中加工的工件数, 在此基础上使得总误工数期望最小。针对工期服从指数分布, 维护时间函数为凹函数的情况, 基于函数性质和指数分布的特点讨论了最优排序需要满足的一些性质, 给出该问题的最优排序; 针对工期服从均匀分布, 维护时间函数为线性函数的情况, 给出了一个最优算法。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    13. 具有两类顾客和灾难到达的故障流体模型的均衡分析
    杨磊, 徐秀丽
    运筹学学报(中英文)    2025, 29 (1): 159-171.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.013
    摘要63)   HTML1)    PDF(pc) (1092KB)(15)    收藏

    本文对两类顾客且有灾难到达的全故障流体模型进行经济学分析, 灾难到达会清空系统迫使顾客离开。假设到达的顾客根据“收益-成本”效用函数决定是否进入。构建线性微分方程组, 在完全可见和几乎可见两种信息水平下利用矩阵分析法得出个体止步阈值和单位时间内的社会收益函数, 最后通过数值算例讨论参数对于社会收益的影响。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    14. 一种求解低秩矩阵补全的惯性加速交替方向法
    闫喜红, 唐晓妮
    运筹学学报(中英文)    2025, 29 (1): 172-184.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.014
    摘要75)   HTML1)    PDF(pc) (2554KB)(30)    收藏

    交替方向法作为求解矩阵补全问题的经典方法之一, 具有能够将一个极小化问题分解成多个规模更小、更容易求解的子问题的优势, 近年来在图像处理和数据分析等领域备受青睐。本文采用交替方向法的框架, 结合惯性策略, 提出了一种求解矩阵补全问题的惯性加速交替方向法。新算法在每步迭代中, 对于其中一部分变量利用交替方向法的前两次迭代点外推得到新一步的迭代点, 从而提高计算效率。本文在合理的假设条件下, 证明了新算法的收敛性。最后, 通过随机矩阵补全的数值实验及图像修复的实例验证了新算法的有效性和可行性。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    15. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图
    杨禹, 朱忠熏, 周鋆鹏
    运筹学学报(中英文)    2025, 29 (1): 185-197.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.015
    摘要64)   HTML0)    PDF(pc) (841KB)(14)    收藏

    对于一个$k$一致超图$H=(V, E)$, 设$B (H)$是它的关联矩阵且$\mathcal{Q}(H)=B (H) B (H)^{\top}$是它的无符号拉普拉斯矩阵。$H$的无符号拉普拉斯谱半径是$\mathcal{Q}(H)$的所有特征值的模的最大值。设$\mathcal{H}^n_{k, r}$是具有$n$个点和$r$个悬挂点的连通$k$一致超图的图类。在$\mathcal{H}^n_{k, r}$中, 对于$n-r\geq k$和某些$n-r\in[k-1]$的情形, 本文刻画了具有最大无符号拉普拉斯谱半径的极值超图。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    16. 单圈图的零强迫和全强迫
    李宝欣, 计省进
    运筹学学报(中英文)    2025, 29 (1): 198-206.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.016
    摘要60)   HTML1)    PDF(pc) (715KB)(20)    收藏

    $S\subseteq V$是一个初始着色顶点子集, 它的所有顶点都着黑色, $S$中的每个顶点称为$S$-着色, $G$中所有其他未着色的顶点称为$S$-未着色。若一个着黑色的顶点$v$恰好只有一个未着色的邻点$u$, 则$v$强迫顶点$u$着黑色, 这样的过程称为强迫过程。如果从一个初始顶点集$S$出发, 逐步运用强迫过程直到$G$中所有的顶点都变成黑色, 则称这个初始集$S$$G$的零强迫集(强迫集)。$G$的零强迫集的最小基数用$F (G)$表示, 称为$G$的零强迫数。如果$S$$G$中的导出子图$G[S]$不包含孤立顶点, 则强迫集$S$称为$G$的全强迫集, 全强迫集的最小基数用$F_t (G)$表示, 称为$G$的全强迫数。注意到零强迫数和全强迫数有如下关系, $F (G)\leq F_t (G)\leq 2F (G)$。刻画满足$F (G)=F_t (G)$或者$2F (G)=F_t (G)$的图$G$是有意义的。基于此, 本文在单圈图上刻画了满足$F (G)=F_t (G)$的所有图$G$。此外, 本文研究了给定匹配数为$k$的单圈图$G$的零强迫数的上界, 即$F (G)\leq n-k$, 等号成立当且仅当$G\cong C_4, A_0$。此外, 当$G\not\cong C_4, A_0$时, 本文刻画了使得$F (G)=n-k-1$的所有图$G$

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    17. 具有固定控制数的树的调和指数
    孙晓玲, 高玉斌, 杜建伟
    运筹学学报(中英文)    2025, 29 (1): 207-215.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.017
    摘要62)   HTML0)    PDF(pc) (488KB)(15)    收藏

    为了预测分子的物理、化学性质和生物活性, 科学家们提出了许多拓扑指数。调和指数是著名的Randić指数的一种变形形式, 研究表明该指数能有效地预测化合物的物理化学性质。对具有固定控制数的树的调和指数进行了研究, 通过分析具有固定控制数的树的结构, 利用数学归纳法, 给出了具有固定控制数的树的调和指数的最大值和最小值, 并刻画了达到最值的树。

    参考文献 | 相关文章 | 多维度评价 | 评论0
    18. 积图的Steiner k-hyper Wiener指标
    王朝平, 刘蒙蒙
    运筹学学报(中英文)    2025, 29 (1): 216-224.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.018
    摘要67)   HTML0)    PDF(pc) (561KB)(10)    收藏

    令图G是一个连通图。当$ 2\leqslant k\leqslant n-1$时, 图G的Steiner k-hyper Wiener指标定义为$ {\rm SWW}_{k}(G)=\frac{1}{2}\sum_{S\subseteq V (G), |S|=k}d_{G}(S)+\frac{1}{2}\sum_{S\subseteq V (G), |S|=k}d_{G}(S)^{2}$, 其中$ d_{G}(S)$表示图GS的Steiner距离, 即连通图G中包含点集S的最小连通子图的边数。本文中我们确定了连图和字典积图的Steiner k-hyper Wiener指标的表达式, 给出了笛卡尔积图, 聚类图和冠状图的Steiner k-hyper Wiener指标的下限。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0
    19. 边染色临界图独立数的新下界
    齐林明, 赵伟良, 苗连英
    运筹学学报(中英文)    2025, 29 (1): 225-231.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.019
    摘要64)   HTML0)    PDF(pc) (538KB)(28)    收藏

    1968年,Vizing提出猜想:如果图$G$$\Delta$-临界图, 则其独立数$\alpha (G)$满足$\alpha (G)\leqslant\dfrac{n}{2}$。这一猜想至今仍未解决。本文对于不含$度点的最大度较小的临界图, 证明当最大度$\Delta\in\{3, 4, 5, 6\}$时, 独立数$\alpha (G)\leqslant\dfrac{7\Delta-6}{12\Delta-6}|V|$;当$\Delta\in\{7, 8, 9\}$时, 独立数$\alpha (G)\leqslant\dfrac{4\Delta-3}{7\Delta-3}|V|$

    参考文献 | 相关文章 | 多维度评价 | 评论0
    20. 完全二部图的Gallai猜想
    耿显亚, 柴惠
    运筹学学报(中英文)    2025, 29 (1): 232-238.   DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.020
    摘要74)   HTML0)    PDF(pc) (516KB)(21)    收藏

    $G$是具有$n$个顶点的简单连通图。Gallai于1966年提出关于图的路分解猜想: 每个$n$阶简单连通图$G$都可以被分解为至多$\left\lceil\frac{n}{2}\right\rceil$条路。在本文中, 我们利用算法证明了Gallai猜想对于完全二部图$K_{n_1, n_2}$成立, 这里1≤n2 < n1n1是奇数。结合Constantinou和Ellinas (2018)的结果, 我们证明了对于任意的完全二部图, Gallai猜想成立。

    图表 | 参考文献 | 相关文章 | 多维度评价 | 评论0