Paper Info
Title
A Best Possible Online Algorithm For Parallel Batch Scheduling With Delivery Times And Limited Restart
Abstract
We consider the online scheduling on an unbounded (drop-line) parallel batch machine to minimize the time by which all jobs have been delivered. In this paper, all jobs arrive over time and the running batches are allowed limited restart. Here limited restart means that a running batch which contains restarted jobs cannot be restarted again. A drop-line parallel batch machine can process several jobs simultaneously as a batch, and all jobs in a batch start at the same time, and the completion time of a job equals the sum of its starting time and its processing time. Here we consider the restricted model: all jobs have agreeable processing times and delivery times. We provide a best possible online algorithm H with a competitive ratio of I for the problem on an unbounded parallel batch machine and the corresponding problem on an unbounded drop-line parallel batch machine, respectively.
Year
DOI
Venue
2021
10.1007/s11590-020-01618-8
OPTIMIZATION LETTERS
Keywords
DocType
Volume
Online scheduling, Parallel batch, Drop-line, Limited restart, Delivery nine
Journal
15
Issue
ISSN
Citations 
4
1862-4472
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Hailing Liu1175.09
Xiwen Lu218221.03
Wenjie Li336859.74