Approximation Algorithms for Scheduling with Rejection on Two Unrelated Parallel Machines
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2015, Vol 6, Issue 11
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.
Authors and Affiliations
Feng Lin, Xianzhao Zhang, Zengxia Cai
Keywords
Related Articles
- EP ID EP90324
- DOI 10.14569/IJACSA.2015.061134
- Views 99
- Downloads 0
FPGA Prototyping and Design Evaluation of a NoC-Based MPSoC
Chip communication architectures become an important element that is critical to control when designing a complex MultiProcessor System-on-Chip (MPSoC). This led to the emergence of new interconnection architectures, lik...
An Improved Malicious Behaviour Detection Via k-Means and Decision Tree
Data Mining algorithm which is applied as an anomaly detection system has been considered as one of the essential techniques in malicious behaviour detection. Unfortunately, such detection system is known for its inclina...
Design of ANFIS Estimator of Permanent Magnet Brushless DC Motor Position for PV Pumping System
This paper presents a new scheme for PMBLDC (permanent magnet brushless direct current) rotor position estimation based an ANFIS (adaptive network fuzzy inference system) estimator. The operation of such motor requires a...
A Guideline for Decision-making on Business Intelligence and Customer Relationship Management among Clinics
Business intelligence offers the capability to gain insights and perform better in decision-making by using a particular set of technologies and tools. A company’s success to a certain extent depends on customers. The co...
Performance Comparison between Merge and Quick Sort Algorithms in Data Structure
In computer science field, one of the basic operation is sorting. Many sorting operations use intermediate steps. Sorting is the procedure of ordering list of elements in ascending or descending with the help of key valu...