Research Article

Online scheduling problem of two flow shop with lookahead interval and incompatible job family

  • Qian XIA ,
  • Xingong ZHANG
Expand
  • 1. School of Mathematical Science, Chongqing Normal University, Chongqing 401331, China

Received date: 2021-11-29

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

Abstract

This paper studies on-line scheduling problem on two unit flowshop machines, in which there exist unbounded batch processing of two incompatible job families and lookahead intervals. The unit flowshop is that the processing time of any job is 1 at two machines. The jobs arrive on time. The goal is to minimize the maximum completion time of the jobs. At time $t$, the lookahead interval means on-line algorithm can predict the information of arriving workpieces in the interval $(t, t+\beta]$. Incompatible workpieces family means that workpieces belonging to different workpieces family cannot be arranged in the same batch. For this problem, we provide a best possible online algorithm $A_1(\beta)$ of competitive ratio $1+\alpha$ for $0 \leqslant \beta<1$, where $\alpha$ is the positive root of the equation $3 \alpha^{2}+(\beta+2) \alpha+\beta-2=0$.

Cite this article

Qian XIA , Xingong ZHANG . Online scheduling problem of two flow shop with lookahead interval and incompatible job family[J]. Operations Research Transactions, 2025 , 29(4) : 103 -111 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.009

References

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 Zhang G C , Cai X Q , Wong C K .Optimal online algorithms for scheduling on parallel batch processing machines[J].ⅡE Transactions,2003,35,175-181.
3 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.
4 Fu R Y , Tian J , Yuan J J .On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs[J].Journal of Scheduling,2009,12,91-97.
5 Chai X , Li W H , Zhu Y J .Online scheduling to minimize weighted flow time on a bounded parallel-batch machine[J].Annals of Operations Research,2021,298,79-93.
6 李文华, 翟威娜, 柴幸, 等.具有两个不相容工件族单位工件的有界分批在线排序问题[J].运筹学学报,2019,23(4):105-110.
7 杨素芳, 李文华.具有前瞻区间的两个工件组单机在线排序问题[J].运筹学学报,2012,16(2):115-120.
8 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.
9 李文华, 柴幸, 袁航, 等.平行机上带有前瞻区间的不相容工件组在线排序问题[J].运筹学学报,2015,19(4):121-126.
10 Li W H , Zhang Z K , Yang S F .Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead[J].Information Processing Letters,2012,112,292-297.
11 Jiao C W , Yuan J J , Feng Q .Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookhead[J].Asia-Pacific Journal of Operational Research,2019,36,1950024.
12 Graham R L , Lawler E L , Lenstra J K , et al.Optimization and approximation in deterministic sequencing and scheduling: A survey[J].Annals of Discrete Mathematics,1979,5,646-675.
Outlines

/