J4 ›› 2013, Vol. 26 ›› Issue (6): 9-13.doi: 10.3976/j.issn.1002-4026.2013.06.003

• Article • Previous Articles     Next Articles

Three singlemachine scheduling problem with rejection cost

 WEI Fei, LIU Shou-Peng   

  1. Binzhou Medical University, Yantai 264003, China
  • Received:2013-06-04 Published:2013-12-20 Online:2013-12-20

Abstract:

       Our objective is to minimize the sum of the makespan of the accepeted jobs and the total rejection cost of the rejected jobs. We present a new online algorithm for a special case of three machines. We also analyze its competitive ratio.

Key words: online scheduling, competitive ratio, uniform machine

CLC Number: 

  • O223

Open Access This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0), which permits third parties to freely share (i.e., copy and redistribute the material in any medium or format) and adapt (i.e., remix, transform, or build upon the material) the articles published in this journal, provided that appropriate credit is given, a link to the license is provided, and any changes made are indicated. The material may not be used for commercial purposes. For details of the CC BY-NC 4.0 license, please visit: https://creativecommons.org/licenses/by-nc/4.0