工件加工时间非增的并行分批排序问题的最优在线算法

• 作者: 农庆琴 苗利辉
• 来源期刊: 中国海洋大学学报（自然科学版）
• 学科: 数学
• 关键词: 排序 并行批 在线 算法 竞争比
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 研究论文
• 页码范围: 126-130
• 页数: 5页
• 分类号: O22
• 字数: 4547字
• 语种: 中文
• DOI: 10.16441/j.cnki.hdxb.20140295

摘要

研究以最小化最大完工时间为目标、批容量有界的并行分批在线排序问题.相应排序模型中有n个相互独立的工件要在一台批处理机上加工,每个工件Jj(1≤j≤n)具有一到达时间rj和加工时间pj,工件的加工时间非增,即对于任意2个工件.Ji和Jj,如果ri≤rj,则pi≥pj.批处理机每次可同时加工至多B(B＜n)个工件.同一批中的工件同时开工,同时完工,任一工件的信息(包括它的到达时间、加工时间)需等到它到达时系统才能获取,研究任务是设计一个在线算法对工件进行合理地分批和排序以使得最大完工时间达到最小.首先证明该在线排序问题不存在竞争比小于1+α(其中α2+α=1)的在线算法,然后设计一在线算法,证明它的竞争比等于1+α,从而证明它的最优性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	农庆琴	中国海洋大学数学科学学院	5	5	1.0	2.0
2	苗利辉	中国海洋大学数学科学学院	1	1	1.0	1.0