有界平行批处理机的在线排序问题

摘要：

主要研究的是在线运输排序问题,即研究m台有界平行批处理机上考虑工件运输的在线排序问题.工件按时间在线到达,即一个工件只有在被释放之后才能知道它的一切信息.这些工件首先要在平行批处理机上分批加工,然后加工完成的工件再被一个运输车辆运送给某个顾客.当车辆的容量是充分大的时候,给出一个最好可能的在线算法,其竞争比为(5(1/2)+1)/2;当车辆的容量有限时,给出一个竞争比为(5(1/2)+3)/2的在线算法.

In this paper, we consider the online scheduling problem on mbounded parallel-batch machine with job deliver- y. All jobs arrive over time. The jobs are first processed in batches on one of bounded parallel-batch machines and then the completed jobs are delivered in batches by a vehicle to some customer. When the capacity of the vehicle is infinite, we present a best possible online algorithm with the competitive ratio of （√-＋1）/2. When the capacity of the vehicle is finite, we give an online algorithm with the competitive ratio of （√5＋ 3）/2.

作者：

刘其佳 冯琪

机构地区：

河南农业大学信息与管理科学学院 中原工学院理学院

出处：

《betway官方app 学报：自然科学版》 CAS 北大核心 2015年第5期8-11,65,共5页

基金：

国家自然科学基金(11401604 11401605) 河南省基础与前沿技术研究计划资助(132300410392)

关键词：

排序 在线算法 运输时间 竞争比

Scheduling online algorithm job delivery competitive ratio

分类号：

O223 [理学—运筹学与控制论]

有界平行批处理机的在线排序问题.pdf