Paper Info
Title
Online Algorithms for Batch Machines Scheduling with Delivery Times.
Abstract
We consider online scheduling on m batch machines with delivery times. In this paper online means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J j, its processing time and delivery time are denoted by p j and q j, respectively. We first consider a restricted model: the jobs have agreeable processing and delivery times, i.e., for any two jobs J i and J j, p i > p j implies q i ≥ q j . For the restrict case, we provide a best possible online algorithm with competitive ratio 1 + α m, where α m > 0 is determined by. Then we present an online algorithm with a competitive ratio of for the general case. © 2013 Springer-Verlag Berlin Heidelberg.
Year
DOI
Venue
2013
10.1007/978-3-642-38768-5_12
COCOON
Keywords
Field
DocType
batch machine,delivery times,online algorithm,scheduling
Online algorithm,Discrete mathematics,Combinatorics,Computer science,Scheduling (computing),Competitive analysis
Conference
Volume
Issue
ISSN
7936 LNCS
null
16113349
Citations 
PageRank 
References 
0
0.34
12
Authors
2
Name
Order
Citations
PageRank
Peihai Liu1526.01
Xiwen Lu218221.03