位置：成果数据库 > 期刊 > 期刊详情页
具有维修时间的两台平行机在线排序
  • ISSN号：1672-6871
  • 期刊名称：河南科技大学学报(自然科学版)
  • 时间：2011.12.12
  • 页码：11-13+18+5
  • 分类：O223[理学—运筹学与控制论;理学—数学]
  • 作者机构：[1]中原工学院理学院,河南郑州450007, [2]郑州大学数学系,河南郑州450052
  • 相关基金：国家自然科学基金项目（10971201 61070229）; 河南省科技攻关项目（09210221014）
  • 相关项目：网络可靠性参数的优化研究
作者： 冯琪|财玉华|
关键词： 平行机排序, 维修时间, 在线算法, 竞争比, Parallel machines scheduling, Maintenance time, On-line algorithm, Competitive ratio
中文摘要：

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的。对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形。通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法。

英文摘要：

In scheduling problems,the machines need to be repaired because of breakdowns or other reasons.Therefore,maintenance time during the processing of jobs is considered.For scheduling problems of two parallel identical machines with common maintenance time intervals and resumable availability,its on-line version was researched.In this paper,the lower bound of competitive ratio no less than 2 for arbitrary on-line algorithm by analysing different cases is proved.Moreover,a best possible on-line algorithm with competitive ratio no more than 2 is given.

同期刊论文项目
网络可靠性参数的优化研究
期刊论文 60 会议论文 2
平行机分组工件排序的多面体方法
期刊论文 34
同项目期刊论文
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-困难性
两个带有分批费用的单机平行分批排序问题
最小化时间表长和最大加工运输时间的单机继列批在线排序
期刊信息
  • 《河南科技大学学报：自然科学版》
  • 北大核心期刊（2011版）
  • 主管单位:河南省教育厅
  • 主办单位:河南科技大学
  • 主编：苏娟华
  • 地址：河南省洛阳市开元大道263号
  • 邮编：471023
  • 邮箱：hkdxbz@haust.edu.cn
  • 电话：0379－64231476
  • 国际标准刊号：ISSN：1672-6871
  • 国内统一刊号：ISSN：41-1362/N
  • 邮发代号:36-285
  • 获奖情况:
  • 1999年全国优秀高校自然科学学报及教育部优秀科技...,全国高校自然科学优秀学报,河南省优秀科技期刊
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国化学文摘（网络版）,波兰哥白尼索引,德国数学文摘,英国科学文摘数据库,中国中国科技核心期刊,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）
  • 被引量:4775