Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts  

作　　者：Hai-Ling Liu Xi-Wen Lu 

机构地区：[1]Department of Mathematics,East China University of Science and Technology,Shanghai 200237,China [2]College of Science,Henan University of Engineering,Zhengzhou 451191,Henan,China

出　　处：《Journal of the Operations Research Society of China》2022年第1期113-131,共19页中国运筹学会会刊（英文）

基　　金：This research was supported by the National Natural Science Foundation of China(Nos.11701148,11871213 and 11571321);Henan University of Engineering(No.D2016017).

摘　　要：The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper.Here,online means that jobs arrive over time and the characteristics of a job become known until it arrives.Limited restarts mean that once a running batch contains at least one restarted job,it cannot be restarted again.The goal is to minimize the time by which all jobs have been delivered.We consider a restricted model that the delivery time of each job is no more than its processing time.We present a best possible online algorithm with a competitive ratio of 3/2 for the problem.

关 键 词：Online scheduling Parallel batch Limited restart Delivery time 

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