Online algorithms for scheduling two parallel machines with a single server. (20th November 2014)

• Record Type: Journal Article
• Authors: Jiang, Yiwei; Yu, Feng; Zhou, Ping; Hu, Jueliang
• Is Part Of: International transactions in operational research. Volume 22:Number 5(2015:Sep.)
• Page Start: 913
• Page End: 927
• Publication Date: 2014-11-20
• Subjects: Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12136
• Languages: English
• ISSNs: 0969-6016

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>We consider an online scheduling problem on two identical parallel machines with a single server. Jobs arrive one by one and each job has to be loaded by the server before being processed on one of the machines, and unloaded immediately by the server after its processing. Both loading and unloading times are equal to one time unit. The goal is to minimize the makespan. For the variant of the problem involving both loading and unloading operations, we present an online algorithm with competitive ratio of 5/3. For the variant with loading operation only, we show that the competitive ratio of list scheduling is at least 8/5 and provide an improved online algorithm with competitive ratio of 11/7. Finally, we discuss the lower bounds for these problems. We show that both variants have a lower bound of 3/2. Furthermore, we show that the lower bound of the first variant is at least 8/5 if the online algorithm satisfies a certain constraint.</p> </abstract>