检索结果-内蒙古大学图书馆

中国管理科学 2022年第11期30卷 159-169页

作者：苏志雄魏汉英张静文乞建勋南昌工程学院工商管理学院江西南昌330099 西北工业大学管理学院陕西西安710072 华北电力大学经济与管理学院北京102206

资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题:项目某环节... 详细信息

资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题:项目某环节的一系列平行工序,可用资源量只有一半,各资源可重复利用且具有相应多功能,但最多能承担2个工序,需将这些工序两两排列成对,实现项目工期最短。本文首先探索问题“局域性”特征,量化局域调度对项目工期的影响;基于此,构建只涵盖“局域调度工序”的0-1规划模型;再者,发展整数规划强对偶理论,结合Dangzig-Wolfe分解等方法,提出多项式时间的精确算法;最后通过算例测试,验证算法优势,例如,计算大规模算例的最优解,运用该算法比常规精确方法可快数万倍以上。

关键词：资源受限项目调度整数规划强对偶多项式时间精确算法 Dangzig-Wolfe分解

来源：评论

学校读者我要写书评

暂无评论

赋权二部图上的伪匹配问题

赋权二部图上的伪匹配问题

引用

作者：李伟云南大学

学位级别：硕士

本文研究了赋权二部图上的伪匹配问题。描述如下：给定赋权二部图$G=(U\cup V,E;f,g;w)$，其中$f:U\longrightarrow \mathbb{N}$，$g:V\longrightarrow \mathbb{N}$，$w:E\longrightarrow \mathbb{R}^{+}$。如果边子集$M\subseteq E$满足对任意$u\in U$，$deg_{M}(u)\geq f(u)$，对任意$v\in V$，$deg_{M}(v)\leq g(v)$，称$M$是一个$(f,g)$-伪匹配。具体研究了两类$(f,g)$-伪匹配问题：(1) 最小权重$(f,g)$-伪匹配问题：定义$(f,g)$-伪匹配$M$的权重$w(M)=\sum_{e\in M}w(e)$，找到一个$(f,g)$-伪匹配$M$，目标是使得$w(M)$最小；(2) 最小累加求和权重$(f,g)$-伪匹配问题：定义$(f,g)$-伪匹配$M$的权重$\widetilde{w}(M)=\sum_{v\in V}\widetilde{w}_{M}(v)$，其中$\widetilde{w}_{M}(v)=\sum_{i=1}^{deg_{M}(v)}(deg_{M}(v)-i+1)\cdot w_i$，$w_1\leq w_2\leq \dots \leq w_{deg_{M}(v)}$是$M$中与顶点$v$关联边上权重的非递减排序，找到一个$(f,g)$-伪匹配$M$，目标是使得$\widetilde{w}(M)$最小。令$B=\sum_{u \in U}f(u)$，$n=\max\{|U|,|V|\}$，$m=|E|$。该论文得到如下结果：(1) 设计了算法$\operatorname{\mathcal{A}}_{MW(f,g)-QM}$解决最小权重$(f,g)$-伪匹配问题，算法的时间复杂度是$O(Bn(n+m))$；(2) 设计了算法$\operatorname{\mathcal{A}}_{MASW(f,g)-QM}$解决最小累加求和权重$(f,g)$-伪匹配问题，算法的时间复杂度是$O(Bn^算法m)$。

关键词：赋权二部图 (f, g)-伪匹配最小费用流算法多项式时间精确算法

来源：评论

学校读者我要写书评

暂无评论

区间图连通支配与k-元组支配问题研究

区间图连通支配与k-元组支配问题研究

引用

作者：周星宏重庆理工大学

学位级别：硕士

图的支配理论富有趣味性和实用性,是图论和计算机领域的研究热点之一,在急救设备的投放、电子商务、传感器网络寿命、光网络中转换器的放置、社交网络、智慧交通等诸多领域都有重要应用。区间图作为对现实问题进行建模的离散数学结构,... 详细信息

图的支配理论富有趣味性和实用性,是图论和计算机领域的研究热点之一,在急救设备的投放、电子商务、传感器网络寿命、光网络中转换器的放置、社交网络、智慧交通等诸多领域都有重要应用。区间图作为对现实问题进行建模的离散数学结构,频繁出现在VLSI设计、电路路由、遗传学、计算机编译器设计、调度问题和其他组合问题中。因此,研究区间图的支配理论有深刻的现实意义。目前关于在区间图中寻找最小连通支配集和最小k-元组支配集的算法不甚简洁。本文围绕区间图的结构性质及支配理论,通过理论分析与实例验证,对以上两种支配集问题设计高效实用的算法,进而为支配集相关问题的发展提供理论依据。针对区间图最小连通支配问题,本文首先回顾Sudhakaraiah等人提出的求解区间图最小连通支配集算法,并指出该算法在输出结果上的不适用之处。然后设计在区间图中寻找最小连通支配集清晰简洁的线性时间精确算法,并通过实例验证和理论分析证明算法的正确性与有效性,进一步得到该算法时间和空间复杂度为O（n+m）。最后,研究单位区间图上的最小外连通支配集问题,并得出若干相关结论。针对区间图最小k-元组支配问题,本文首先对该问题设计多项式时间精确算法,且算法的时间复杂度指数与k无关,为O（n2）。然后以k=4为例进行算法分析和实例验证。最后,在实例分析的佐证下,得到区间图最小k-元组支配集的元素个数与前导顶点集合L的元素个数间的关系以及每个区间图都有唯一确定的k-元组基础图等结论。

关键词：支配集区间图连通支配集 k-元组支配集多项式时间精确算法

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：