| 单机上带有可变前瞻区间的分批在线排序问题 |
| |
| 引用本文： | 王利博,李文华,余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140. DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.010 |
| |
| 作者姓名： | 王利博 李文华 余丹 |
| |
| 作者单位： | 1. 郑州大学数学与统计学院, 河南郑州 450001 |
| |
| 基金项目： | 国家自然科学基金(11971443);国家自然科学基金(11771406) |
| |
| 摘 要： | 本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达，目标是最小化时间表长。在时刻$t$，在线算法能够预见到$（t，t+Delta（t）]$内到达工件的信息，这里前瞻区间的长度$Delta（t）=beta p_{max}（t）$并非定长，其中$p_{max}（t）$表示在$t$时刻及之前到达工件的最大加工时长，$betain（0，1）$是常数。本文对于工件加工时长的一般情形，给出了当 0<β≤1/6 时最好可能的在线算法；对于工件加工时长被限制在一个区间的情形，给出了当 0<β<1 时最好可能的在线算法。
|
| 关 键 词： | 分批排序 在线算法 前瞻区间 时间表长 竞争比 |
| 收稿时间： | 2021-05-10 |
Online scheduling on single batch machine with variable lookahead interval |
| |
| Affiliation: | 1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, Henan, China |
| |
| Abstract: | This paper investigates the online scheduling on an unbounded parallel-batch machine with variable lookahead interval to minimize makespan. Online means that jobs arrive over time. At any time $t$, an online algorithm can foresee the information of the jobs arriving in $(t, t+Delta(t)]$, where $Delta(t)=beta p_{max}(t)$ is the length of the lookahead interval which is not invariable, $p_{max}(t)$ is the maximum processing time of the jobs arriving at or before $t$ and $betain(0, 1)$ is a constant. On the general case of processing time, we give an online algorithm which is the best possible for 0<β≤1/6. When the processing times of all jobs are restricted in an interval, we give the best possible online algorithm for 0<β<1. |
| |
| Keywords: | batch scheduling online algorithm lookahead interval makespan competitive ratio |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载免费的PDF全文 |
|
