| 有界平行批处理机的在线排序问题 |
| |
| 作者单位： | ;1.河南农业大学信息与管理科学学院;2.中原工学院理学院 |
| |
| 摘 要： | 主要研究的是在线运输排序问题,即研究m台有界平行批处理机上考虑工件运输的在线排序问题.工件按时间在线到达,即一个工件只有在被释放之后才能知道它的一切信息.这些工件首先要在平行批处理机上分批加工,然后加工完成的工件再被一个运输车辆运送给某个顾客.当车辆的容量是充分大的时候,给出一个最好可能的在线算法,其竞争比为(5(1/2)+1)/2;当车辆的容量有限时,给出一个竞争比为(5(1/2)+3)/2的在线算法.
|
| 关 键 词： | 排序 在线算法 运输时间 竞争比 |
Online Scheduling on Bounded Parallel-batch Machines |
| |
| Institution: | ,College of Information and Management Science,Henan Agricultural University,College of Science,Zhongyuan University of Technology |
| |
| Abstract: | In this paper,we consider the online scheduling problem on mbounded parallel-batch machine with job delivery.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(5(1/2)+1)/2.When the capacity of the vehicle is finite,we give an online algorithm with the competitive ratio of(5(1/2)+3)/2. |
| |
| Keywords: | Scheduling online algorithm job delivery competitive ratio |
| 本文献已被 CNKI 等数据库收录！ |
|
