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

作     者：农庆琴 苗利辉 NONG Qing-Qin;MIAO Li-Hui

作者机构：中国海洋大学数学科学学院山东青岛266100 

基　　金：国家自然科学基金项目(11201439 11271341) 教育部博士点专项基金新教师基金项目(20120132120001) 山东省自然科学基金项目(ZR2012AQ12)资助~~ 

出 版 物：《中国海洋大学学报（自然科学版）》 (Periodical of Ocean University of China)

年 卷 期：2017年第47卷第1期

页      码：126-130页

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

主 题 词：排序 并行批 在线 算法 竞争比 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.16441/j.cnki.hdxb.20140295

馆 藏 号：203210519...