检索结果-南通市图书馆

一个具有两类工件的多目标排序的NP-困难性

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

运筹学学报 2007年第4期11卷 121-126页

作者：冯琪原晋江中原工学院理学院郑州450007

文章考虑具有两个工件集的单机排序问题.第一个工件集J1以加权完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小,并证明该问题是强NP-困难的.

关键词：运筹学排序多目标计算复杂性 NP-困难的

在线全文

学校读者我要写书评

暂无评论

小直径图的导出匹配覆盖(英文)

运筹学学报 2008年第2期12卷 17-24页

作者：董丽原晋江信阳师范学院数学与信息科学学院信阳464000 郑州大学数学系郑州450052

设G是一个图,而M_1,M_2,…,M_k是G的k个导出匹配.称{M_1,M_2,…,M_k)是图G的一个k-导出匹配覆盖,若V(M_1)∪V(M_2)∪…∪V(M_k)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图... 详细信息

设G是一个图,而M_1,M_2,…,M_k是G的k个导出匹配.称{M_1,M_2,…,M_k)是图G的一个k-导出匹配覆盖,若V(M_1)∪V(M_2)∪…∪V(M_k)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解.

关键词：运筹学导出匹配导出匹配覆盖 NP-完备多项式可解

相容工件系统的最小化最大延迟与误工和的重新排序(英文)

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2007年第1期11卷 39-48页

作者：慕运动原晋江郑州大学数学系

在单机重新排序问题中,一个原始工件集已经排好顺序,使得给定的目标函数最小．当一个新的工件集到来时就会产生一些错位,决策者需要插入新工件到原来排序中而还不能过分打乱它们的顺序．该论文首先研究了当工件加工时间和工期相容时,在... 详细信息

在单机重新排序问题中,一个原始工件集已经排好顺序,使得给定的目标函数最小．当一个新的工件集到来时就会产生一些错位,决策者需要插入新工件到原来排序中而还不能过分打乱它们的顺序．该论文首先研究了当工件加工时间和工期相容时,在错位量限制的条件下最小化最大延迟问题;也研究了当工件加工时间相同或工件工期相同时,在错位量限制的条件下最小化误工和问题．对这些问题,给出了好的算法．

关键词：运筹学重新排序相容序列错位时间错位单机

工件可自由下线最小化总完工时间的有界平行分批排序

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2018年第1期22卷 32-41页

作者：酒明珠高园原晋江郑州大学数学与统计学院郑州450001

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完... 详细信息

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批■有一个开工时间S,那么包含在批■中的每一个工件乃的开工时间定义为S,而它的完工时间定义为S+p_j,这里p_j是工件J_j的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(n^(b(b-1))的动态规划算法.

关键词：分批排序工件可自由下线总完工时间

PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

在线全文

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2004年第3期19卷 245-251页

作者：杨爱峰原晋江 Dept. of Appl. Math. South China Univ. of Tech. Guangdong 510640ChinaDept. of Math.Zhengzhou Univ.Henan 450052China Dept. of Math. Zhengzhou Univ.Henan 450052China

Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.

关键词： induced matching partition coloring

单可变资源最小化加权完工时间和排序问题的强NP-困难性(英文)

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2010年第1期14卷 31-36页

作者：原晋江王勤郑州大学数学系郑州450052 中国计量学院数学系杭州310018

Baker和Nuttle提出了下述单可变资源排序问题:n个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困... 详细信息

Baker和Nuttle提出了下述单可变资源排序问题:n个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.

关键词：运筹学排序资源的可利用率资源需求加权完工时间和强NP-困难性

最小最大树划分的近似算法与最小和树划分的精确算法

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2006年第4期10卷 115-121页

作者：农庆琴原晋江郑州大学数学系郑州450052

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划... 详细信息

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．

关键词：运筹学划分支撑树多项式时间算法近似算法

DEGREE CONDITIONS OF INDUCED MATCHING EXTENDABLE GRAPHS

在线全文

学校读者我要写书评

暂无评论

Applied Mathematics(A Journal of Chinese Universities) 2000年第1期15卷 1-6页

作者： Liu Yan\ yuan jinjiang\ Wang Shiying Dept.ofSystem Sci.and Math.,Zhengzhou Univ.,Zhengzhou 450052 Dept. of System Sci. and Math. Zhengzhou Univ.

A simple graph G is induced matching extendable,shortly IM\|extendable,if every induced matching of G is included in a perfect matching of G .The degree conditions of IM\|extendable graphs are researched in this *** main results are as follows:\;(1) 2n/32n/32n/32n/3 is the minimum integer δ such that every graph with minimum degree at least δ is IM\|extendable,where n=|V(G)|≥6 is even.\;(2) is the minimum integer δ such that every graph with minimum degree at least δ is IM\|extendable,where n=|V(G)|≥6 is even.\;(2) (2n-2)/3 is the minimum integer k such that, for k′≥k ,every k ′ regular graph with vertex number n is IM\|extendable,where n=|V(G)| is even, n ≥8 and n ≠10.

关键词： Perf-ec-tmatching inducedmatching extendable.

在线全文

学校读者我要写书评

暂无评论

单机主次指标排序问题(英文)

运筹学学报 2005年第2期9卷 63-67页

作者：孙玉芹原晋江同济大学应用数学系上海200092 郑州大学数学系郑州450052

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax.在同工期且准备时间和工期具有一致性的情形下,给出了该问题的允许中断抢先的多项式时间算法.

关键词：排序问题指标单机 pm 多项式时间算法准备时间一致性工期