Facebook pixel tracking

The Science and Information (SAI) Organization publishes open-access peer-reviewed journals in computer science and artificial intelligence.

Contact Info
Email info@thesai.org
Website thesai.org
Follow Us
Contact Info
Email info@thesai.org
Follow Us
Research Article | Open Access |

Approximation Algorithms for Scheduling with Rejection on Two Unrelated Parallel Machines

Author 1: Feng Lin Author 2: Xianzhao Zhang Author 3: Zengxia Cai
International Journal of Advanced Computer Science and Applications (IJACSA) · Vol. 6, No. 11 · Published 2015

DOI: https://doi.org/10.14569/IJACSA.2015.061134

Download PDF Cite Call for Papers

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.

Keywords

Scheduling Rejection Approximation algorithm Linear programming Rounding

How to Cite this Article

Lin, F., Zhang, X., & Cai, Z. (2015). Approximation Algorithms for Scheduling with Rejection on Two Unrelated Parallel Machines. International Journal of Advanced Computer Science and Applications, 6(11). https://doi.org/10.14569/IJACSA.2015.061134

Lin, Feng, et al.. "Approximation Algorithms for Scheduling with Rejection on Two Unrelated Parallel Machines." International Journal of Advanced Computer Science and Applications, vol. 6, no. 11, 2015, https://doi.org/10.14569/IJACSA.2015.061134.

@article{Lin2015,
  title     = {Approximation Algorithms for Scheduling with Rejection on Two Unrelated Parallel Machines},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {6},
  number    = {11},
  year      = {2015},
  publisher = {The Science and Information Organization},
  author    = {Feng Lin and Xianzhao Zhang and Zengxia Cai},
  doi       = {10.14569/IJACSA.2015.061134},
  url       = {https://doi.org/10.14569/IJACSA.2015.061134}
}

Open Access — licensed under a Creative Commons Attribution 4.0 International License. Unrestricted use, distribution, and reproduction in any medium, even commercially, as long as the original work is properly cited.

Back to Issue
IJACSA Journal Cover

IJACSA