Parallel machine scheduling with job delivery coordination

Jianming Dong, Xueshi Wang, Liliang Wang, Jueliang Hu

Abstract


We analyse a parallel (identical) machine scheduling problem with job delivery to a single customer. For this problem, each job needs to be processed on \(m\) parallel machines non-pre-emptively and then transported to a customer by one vehicle with a limited physical capacity. The optimization goal is to minimize the makespan, the time at which all the jobs are processed and delivered and the vehicle returns to the machine. We present an approximation algorithm with a tight worst-case performance ratio of \(7/3-1/m\) for the general case, \(m\ge 3\).


doi:10.1017/S1446181117000190

Keywords


scheduling, job delivery, bin packing, approximation algorithm.



DOI: http://dx.doi.org/10.21914/anziamj.v58i0.11054



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.