单机上带有可变前瞻区间的分批在线排序问题

展开
  • 1. 郑州大学数学与统计学院, 河南郑州 450001
李文华   E-mail: liwenhua@zzu.edu.cn

收稿日期: 2021-05-10

  网络出版日期: 2022-03-14

基金资助

国家自然科学基金(11971443);国家自然科学基金(11771406)

Online scheduling on single batch machine with variable lookahead interval

Expand
  • 1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, Henan, China

Received date: 2021-05-10

  Online published: 2022-03-14

摘要

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$(t,t+\Delta(t)]$内到达工件的信息,这里前瞻区间的长度$\Delta(t)=\beta p_{\max}(t)$并非定长,其中$p_{\max}(t)$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in(0,1)$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。

本文引用格式

王利博, 李文华, 余丹 . 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022 , 26(1) : 134 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.010

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 $\beta\in(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.

参考文献

1 Zhang G C , Cai X Q , Wong C K . On-line algorithms for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48, 241- 258.
2 Tian J , Cheng T C E , Ng C T , et al. Online scheduling on unbounded parallel-batch machines to minimize the makespan[J]. Information Processing Letters, 2009, 109, 1211- 1215.
3 Liu P H , Lu X W , Fang Y . A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines[J]. Journal of Scheduling, 2012, 15, 77- 81.
4 Tian J , Fu R Y , Yuan J J . Online over time scheduling on parallel-batch machines: A survey[J]. Journal of the Operations Research Society of China, 2014, 2, 445- 454.
5 Li W H , Zhang Z K , Yang S F . Online algorithms for scheduling unit length jobs on parallelbatch machines with lookahead[J]. Information Processing Letters, 2012, 112, 292- 297.
6 杨素芳, 李文华. 具有前瞻区间的两个工件组单机在线排序问题[J]. 运筹学学报, 2012, 16, 115- 120.
7 Li W H , Yuan J J , Yang S F . Online scheduling of incompatible unit-length job families with lookahead[J]. Theoretical Computer Science, 2014, 543, 120- 125.
8 李文华, 柴幸, 袁航, 等. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19, 121- 126.
9 Jiao C W , Yuan J J , Feng Q . Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookahead[J]. Asia-Pacific Journal of Operational Research, 2019, 36, 1950024.
10 Mandelbaum M , Shabtay D . Scheduling unit length jobs on parallel machines with lookahead information[J]. Journal of Scheduling, 2011, 14, 335- 350.
11 Chen C , Zhang H L , Xu Y F . Online machine minimization with lookahead[J]. Journal of Combinatorial Optimization, 2020,
12 Poon C K , Yu W C . A flexible on-line scheduling algorithm for batch machine with infinite capacity[J]. Annals of Operations Research, 2005, 133, 175- 181.
13 Fang Y , Liu P H , Lu X W . Optimal on-line algorithms for one batch machine with grouped processing time[J]. Journal of Combinatorial Optimization, 2011, 22, 509- 516.
文章导航

/