摘要
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.
基金
This research was supported by the National Natural Science Foundation of China(Nos.11701148,11871213 and 11571321)
Henan University of Engineering(No.D2016017).