Scheduling on two parallel machines with two dedicated servers

Yiwei Jiang, Ping Zhou, Huijuan Wang, Jueliang Hu

Abstract


We study a nonpreemptive scheduling on two parallel identical machines with a dedicated loading server and a dedicated unloading server. Each job has to be loaded by the loading server before being processed on one of the machines and unloaded immediately by the unloading server after its processing. The loading and unloading times are both equal to one unit of time. The goal is to minimize the makespan. Since the problem is NP-hard, we apply the classical list scheduling and largest processing time heuristics, and show that they have worst-case ratios, \(8/5\) and \(6/5\), respectively.



doi:10.1017/S1446181117000141

Keywords


scheduling, server, algorithm, worst-case ratio, makespan.



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



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.