Name
Abstract | ||
|---|---|---|
We consider the online unbounded batch scheduling problems on $$m$$ m identical machines subject to release dates and delivery times. Jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Jobs can be processed in a common batch and the batch capacity is unbounded. Once the processing of a job is completed it is independently delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job $$J_j$$ J j , its processing time and delivery time are denoted by $$p_j$$ p j and $$q_j$$ 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$$ J i and $$J_j\\,p_i>p_j$$ J j p i > p j implies $$q_i\\ge q_j$$ q i ¿ q j . For the restrict case, we provide a best possible online algorithm with competitive ratio $$1+\\alpha _m$$ 1 + ¿ m , where $$\\alpha _m>0$$ ¿ m > 0 is determined by $$\\alpha _m^2+m\\alpha _m=1$$ ¿ m 2 + m ¿ m = 1 . Then we present an online algorithm with a competitive ratio of $$1+2/\\lfloor \\sqrt{m}\\rfloor $$ 1 + 2 / ¿ m ¿ for the general case. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s10878-014-9706-4 | J. Comb. Optim. |
Keywords | Field | DocType |
Scheduling,Online algorithm,Batch machines,Delivery times,Competitive ratio | Online algorithm,Combinatorics,Scheduling (computing),Job scheduler,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
29 | 1 | 1382-6905 |
Citations | PageRank | References |
3 | 0.44 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peihai Liu | 1 | 52 | 6.01 |
| Xiwen Lu | 2 | 182 | 21.03 |