工件的释放时间和加工时间具有一致性的单机在线排序问题研究  

Research on the single-machine online schedule in which the jobs’release times and processing times are agreeable

作　　者：李文杰[1] 李钰晶 刘海玲 LI Wenjie;LI Yujing;LIU Hailing(School of Mathematical Sciences,Luoyang Normal University,Luoyang 471934,Henan,China;College of Science,Henan University of Engineering,Zhengzhou 451191,Henan,China)

机构地区：[1]洛阳师范学院数学科学学院,河南洛阳471934 [2]河南工程学院理学院,河南郑州451191

出　　处：《运筹学学报》2022年第2期55-63,共9页Operations Research Transactions

基　　金：河南省自然科学基金(No.222300420503);河南省高校重点基础研究基金(Nos.22A110015,20ZX004,22ZX009);河南省高校青年骨干教师培养计划基金(Nos.2019GGJS202,2018XJGGJS-10)。

摘　　要：工件的释放时间和加工时间具有一致性,是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间,即若r_(i)≥r_(j),则p_(i)≥p_(j)。本文在该一致性约束下,研究最小化最大加权完工时间单机在线排序问题,和最小化总加权完工时间单机在线排序问题,并分别设计出√5+2/2—竞争的最好可能在线算法。There are n jobs J,J,…,Jto be scheduled on the single machine.Each job Jhas a nonnegative arriving time r,a positive processing time p,and a nonnegative weight w.We consider one restricted model:the jobs have agreeable release times and processing times(i.e.,if r_(i)≥r_(j),then p_(i)≥p_(j)).Under this restricted model,we study the single-machine online schedule to minimize the maximum weighted completion time of jobs or the total weighted completion times of jobs.We present two best possible online algorithms with the competitive ratio of both√5+2/2.

关 键 词：在线排序 在线算法 一致性 加权完工时间 

分 类 号：O221.7[理学—运筹学与控制论]