Copyright Statement: This is an open access article licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, even commercially as long as the original work is properly cited.
Digital Object Identifier (DOI) : 10.14569/IJACSA.2015.061134
Article Published in International Journal of Advanced Computer Science and Applications(IJACSA), Volume 6 Issue 11, 2015.
Abstract: In this paper, we study the scheduling problem with rejection on two unrelated parallel machines. We may choose to reject some jobs, thus incurring the corresponding penalty. The goal is to minimize the makespan plus the sum of the penalties of the rejected jobs. We first formulate this scheduling problem into an integer program, then relax it into a linear program. From the optimal solution to the linear program, we obtain the two algorithms using the technique of linear programming rounding. In conclusion, we present a deterministic 3-approximation algorithm and a randomized 3-approximation algorithm for this problem.
Feng Lin, Xianzhao Zhang and Zengxia Cai, “Approximation Algorithms for Scheduling with Rejection on Two Unrelated Parallel Machines” International Journal of Advanced Computer Science and Applications(IJACSA), 6(11), 2015. http://dx.doi.org/10.14569/IJACSA.2015.061134