位置：成果数据库 > 期刊 > 期刊详情页
两个代理的单机排序问题的多项式时间算法
  • ISSN号：0253-2395
  • 期刊名称：山西大学学报(自然科学版)
  • 时间：2012.8.8
  • 页码：448-451
  • 分类：O223[理学—运筹学与控制论;理学—数学]
  • 作者机构：[1]郑州大学数学系, [2]中原工程学院理学院, [3]河南工程学院数学科学系, [4]河南理工大学数学与信息科学学院
  • 相关基金：国家自然科学基金(61070229;10971201;10901144); 教育部博士点基金(20111401110005); 河南省教育厅自然科学研究计划项目(2010A110004); 河南省自然科学研究
  • 相关项目：网络可靠性参数的优化研究
作者： 冯琪|孙晓梅|马冉|尚卫萍|
关键词： 排序, 多代理, 多项式时间算法
中文摘要：

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.

同期刊论文项目
平行机分组工件排序的多面体方法
期刊论文 34
无线网络中一些图论与组合优化问题
期刊论文 19 会议论文 4
网络可靠性参数的优化研究
期刊论文 60 会议论文 2
同项目期刊论文
Fault-free Hamiltonian cycles passing through a linear forest in ternary -cubes with faulty edges
Many-to-many disjoint path covers in -ary -cubes
A semi-on-line scheduling problem of two parallel machines with common maintenance time
k元n方体的边容错性
完全偶图的定向图
k元n立方网络的k圈排除问题的递归算法
成本倒推装卸工问题
λ5-最优图的一个充分条件
带有条件故障边的k元2方体的圈嵌入
图是λ5-最优的邻域交条件
图与补图孤立断裂度的关系
Ménage问题的一种粘贴DNA算法
孤立断裂度给定条件下的一类图
泡型图的条件匹配排除
带有条件故障边的3元n方体的圈嵌入
图是λ5-最优的充分条件
一个具有退化的两个代理的排序问题
具有维修时间的两台平行机在线排序
工业生产中一个带有拒绝费用的工件排序问题研究
λ4-最优图的一个充分条件
λ6最优图的充分条件
泡形互连网络的条件连通性度量
图的孤立断裂度
含有两个非临界点的强连通定向图的弧数(英文)
Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube
dge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges
Conditional connectivity of star graph networks under embedding restriction
Embedding hamiltonian paths in k-ary n-cubes with conditional edge faults
Fault tolerance in bubble-sort graph networks
Fault tolerance in k-ary n-cube networks
k-Pancyclicity of k-ary n-Cube Networks under the Conditional Fault Model
Hamiltonian cycles passing through linear forests in k-ary n-cubes
Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements
Embedding long cycles in faulty k-ary 2-cubes
A neighborhood condition for graphs to be maximally k-restricted edge connected
Pancyclicity of ternary n-cube networks under the conditional fault model
Sufficient conditions for maximally edge-connected graphs and arc-connected digraphs
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
用对偶单纯形算法解装卸工问题
A sufficient condition for graphs to be -optimal
Strong matching preclusion for -ary -cubes
Fault-tolerant embedding of cycles of various lengths in k-ary n-cubes
An on-line scheduling problem of parallel machines with common maintenance time
An on-line scheduling problem of paralled machines with common maintenance time
对称群上Cayley图的条件匹配排除数
Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-tra
Ordered and Hamilton Digraphs
两个代理的单机排序问题研究
一类对称群上Cayley图的最优条件匹配排除集
λ5-最优图的邻域交条件
A conjecture on k-transitive digraphs
Ordered and Ordered Hamilton Digraphs
λ5-最优图的邻域交条件
一种基于多维度信任的WSN安全数据融合方法
含有两个非临界点的强连通定向图的弧数
Ménage问题的一种粘贴DNA算法
一个具有退化的两个代理的排序问题
具有维修时间的两台平行机在线排序
工业生产中一个带有拒绝费用的工件排序问题研究
Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan
A note on the single machine scheduling to minimize the number of tardy jobs with deadlines
单可变资源最小化加权完工时间和排序问题的强NP-困难性(英文)
Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespa
Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine
Best semi-online algorithms for unbounded parallel batch scheduling
Online scheduling on batching machines to minimise the total weighted completion time of jobs with p
SOME IMPROVED ALGORITHMS ON THE SINGLE MACHINE HIERARCHICAL SCHEDULING WITH TOTAL TARDINESS AS THE P
Parallel-machine scheduling with deteriorating jobs and rejection
A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan
Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time
Unbounded parallel-batching scheduling with two competitive agents
Group scheduling and due date assignment on a single machine
Preemptive scheduling with simple linear deterioration on a single machine
An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delive
A best possible online algorithm for scheduling equal-length jobs on two machines with chain precede
两个代理的单机排序问题研究
一种基于多维度信任的WSN安全数据融合方法
赋予图均衡方向的欧拉图构造法和圈树分解法
工件带链约束和尺寸的并行批排序
单可变资源最小化加权完工时间和排序问题的强NP-困难性
两个带有分批费用的单机平行分批排序问题
最小化时间表长和最大加工运输时间的单机继列批在线排序
关于极大二部匹配可扩图
Roman domiantion and its variants in unit disk graphs
偶匹配可扩性的极图问题(英文)
关于元爪图的一个性质(英文)
Algorithms for minimum connected capacitated dominating set problem
Two models of two-dimensional bandwidth problems
SQUARE-ROOT RULE OF TWO-DIMENSIONAL BANDWIDTH PROBLEM
A characterization of PM-compact bipartite and near-bipartite graphs
4-regular bipartite matching extendable graphs.
An on-line scheduling problem of parallel machines with common maintenance time
两个代理的单机这排序问题的多项式时间算法
两个代理的单机排序问题研究
基于蛛网模型理论的柑橘生产和价格波动分析
A Property of Claw-free Graphs
基于萤火虫群的无线传感器网络节点定位方法
一种基于粒子群的实际业务流预测算法
期刊信息
  • 《山西大学学报：自然科学版》
  • 北大核心期刊（2011版）
  • 主管单位:山西省教育厅
  • 主办单位:山西大学
  • 主编：杨斌盛
  • 地址：太原市坞城路92号
  • 邮编：030006
  • 邮箱：xbbjb@sxu.edu.cn
  • 电话：0351-7010455
  • 国际标准刊号：ISSN：0253-2395
  • 国内统一刊号：ISSN：14-1105/N
  • 邮发代号:22-42
  • 获奖情况:
  • 边疆七年获山西省一级期刊荣誉（1993-1999）
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国化学文摘（网络版）,英国动物学记录,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）
  • 被引量:5651