Online unbounded batch scheduling on parallel machines with delivery times

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.