Photo from wikipedia
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… Click to show full abstract
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.
Journal Title: Journal of the Operations Research Society of China
Year Published: 2021
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!