English

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (4): 103-111.doi: 10.15960/j.cnki.issn.1007-6093.2025.04.009

• • 上一篇    

具有前瞻区间和不相容工件族的两台流水车间在线排序问题

夏倩, 张新功†   

  1. 重庆师范大学数学科学学院, 重庆 401331
  • 收稿日期:2021-11-29 发布日期:2025-12-11
  • 通讯作者: 张新功 E-mail:zhangxingong@cqnu.edu.cn
  • 基金资助:
    国家自然科学基金重大项目(No.11991022),国家自然科学基金面上项目(No.11971443),重庆市教委重点项目(No.KJZD-K202000501),重庆市科委项目(No.cstc2021jcyj-msxmX0229),重庆市教委研究生教改重点项目(No.YJG182019)

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

XIA Qian, ZHANG Xingong†   

  1. School of Mathematical Science, Chongqing Normal University, Chongqing 401331, China
  • Received:2021-11-29 Published:2025-12-11

PDF

3

摘要： 本文研究两台单位流水作业上, 具有前瞻区间的两个不相容工件族无界批处理的在线排序问题。单位流水车间问题是指任何工件在每台机器上的加工长度均为$1$, 工件按时到达, 目标是最小化最大完工时间。具有前瞻区间是指在时刻$t$, 在线算法能预见$(t,t+\beta]$区间内到达工件的信息。不可相容工件族是指属于不同工件族的工件不能安排在同一批加工。本文提供了一个竞争比为$1+\alpha$的在线算法$A_1(\beta)$, 其中$\alpha=\displaystyle\frac{\sqrt{\beta^{2}-8 \beta+28}-(\beta+2)}{6}$$(\displaystyle\frac{\sqrt{21}-3}{6}<\alpha\leqslant \displaystyle\frac{\sqrt{7}-1}{3})$是方程$3 \alpha^{2}+(\beta+2) \alpha+\beta-2=0$ 的一个正根, 这里$0 \leqslant \beta<1$。

关键词: 在线算法, 前瞻区间, 不相容工件族, 竞争比, 最小化最大完工时间

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$.

Key words: on-line algorithm, lookahead interval, incompatible family, competitive ratio, minimize the maximum completion time

中图分类号: