| 最大化接收工件总权值的批处理机在线排序 |
| |
| 作者单位： | ;1.洛阳师范学院数学科学学院;2.河南师范大学数学与信息科学学院 |
| |
| 摘 要： | 研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p0,一个到达时间r_j≥0,一个权值w_j0,一个必须交货期d_j0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m~2-m)~(1/2)/(2m~2-m).
|
| 关 键 词： | 在线排序 竞争比 批处理机 接收工件总权值 |
Online Batch-machine Scheduling to Maximize Total Weight of the Accepted Jobs |
| |
| Institution: | ,School of Mathematical Sciences,Luoyang Normal University,College of Mathematics and Information Science,Henan Normal University |
| |
| Abstract: | This paper studies the online scheduling on m unbounded batch machines. Each job J_jhas a common processing time p > 0,an arriving time r_j≥0,a weight w_j> 0,a deadline d_j> 0. "Unbounded batch machines"means that one machine can process up to countless jobs simultaneously as a batch. The goal is to determine a preemption-restart schedule which maximizes total weight of the accepted jobs. In this paper,we first design an online algorithm,and then prove that it has a competitive ratio of 3-1/m-( 4m-2)( 2m~2-m)~(1/2)/( 2m~2-m). |
| |
| Keywords: | online scheduling competitive ratio batch machines total weight of the accepted jobs |
| 本文献已被 CNKI 等数据库收录！ |
|
