We consider an online scheduling problem on three parallel and identical machines with two grades of service (GoS) levels. Given are three machines and n independent jobs, each job and machine assigned the GoS levels of 1 or 2. The processing rule is that the job is allowed to be processed on some particular machines only when the GoS level of the job is no less than that of the machine, the jobs arrive over time and the three machines are idle at the same time only when all jobs arrived are completed. The objective is to minimize the makespan. In this paper, we show that any online approximation algorithm for the problem under consideration achieves the competitive ratio is no better than 4 / 3 , even for the case where the GoS levels of machines are 1, 2, 2, respectively. Moreover, we present an approximation algorithm with a competitive ratio of 5 / 3which is better than the best known algorithm whose the competitive ratio is 9 / 5 .
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.