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

Online Scheduling Problem of Unit Flow Shops with Lookahead Interval and Incompatible Job Family

作　　者：张新功 张静仪 夏倩 赵文平 ZHANG Xingong;ZHANG Jingyi;XIA Qian;ZHAO Wenping(School of Mathematics Sciences,Chongqing Normal University,Chongqing 40133l;Chongqing Xiejiawan School,Chongqing,400050;Science City Middle School of Chongqing Bashu Secondary School,Chongqing 401331,China)

机构地区：[1]重庆师范大学数学科学学院,重庆401331 [2]重庆谢家湾学校,重庆400050 [3]重庆巴蜀中学科学城中学,重庆401331

出　　处：《重庆师范大学学报（自然科学版）》2023年第4期1-5,共5页Journal of Chongqing Normal University:Natural Science

基　　金：重庆市教育委员会重点项目(No.KJZD-K202000501);重庆市自然科学基金基础研究与前沿探索专项面上项目(No.cstc2021jcyj-msxmX0229);重庆英才创新创业示范团队项目(No.CQYC20210309536)。

摘　　要：研究对多台单位流水车间上具有前瞻区间的不相容工件族无界批处理的在线排序问题。通过组合优化的方法分类讨论得到问题的下界,对算法Am(β)进行了竞争比分析说明这是该问题最好可能的在线算法。给出了该问题的下界为1+η,其中η是方程(2f-1)η2+(f+β)η+β-f=0的一个正根,这里0≤β<1。同时提供了一个最好可能的在线算法Am(β)。通过竞争比分析说明了算法的可行性。The online sequencing problem of unbounded batch processing of incompatible workpieces with prospective intervals in a multi-unit flow shop is studied.Through the classification and discussion of combinatorial optimization method,the lower bound of the problem is obtained,and the competitive ratio analysis of the algorithm shows that it is the best possible online algorithm.For this problem,the lower bound 1+αis given,whereαis the positive root of the equation(2f-1)α2+(f+β)α+β-f=0.Meanwhile,a best possible online algorithm A_(m)(β)is provided.The feasibility of algorithm is illustrated by competitive ratio.

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

分 类 号：O223[理学—运筹学与控制论]