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 74
- Downloads 0
Performance Comparison of DCT and Walsh Transforms for Watermarking using DWT-SVD
This paper presents a DWT-DCT-SVD based hybrid watermarking method for color images. Robustness is achieved by applying DCT to specific wavelet sub-bands and then factorizing each quadrant of frequency sub-band using sin...
Privacy Preserving Data Mining Approach for IoT based WSN in Smart City
Wireless Sensor Network (WSN) is one of the most fundamental technologies of Internet of Things (IoT). Various IoT devices are connected to the internet by making use of WSN composed of different sensor nodes and actuato...
A Proposed Methodology on Predicting Visitor’s Behavior based on Web Mining Technique
The evolution of the internet in recent decades enlarge the website's reports with the records of user’s activities and behaviors that registered in the web server which can be created automatically in the web access log...
Spectrum Sharing Security and Attacks in CRNs: a Review
Cognitive Radio plays a major part in communication technology by resolving the shortage of the spectrum through usage of dynamic spectrum access and artificial intelligence characteristics. The element of spectrum shari...
Multiobjective Optimization for the Forecasting Models on the Base of the Strictly Binary Trees
The optimization problem dealing with the development of the forecasting models on the base of strictly binary trees has been considered. The aim of paper is the comparative analysis of two optimization variants which ar...