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 72
- Downloads 0
Secured Wireless Communication using Fuzzy Logic based High Speed Public-Key Cryptography (FLHSPKC)
In this paper secured wireless communication using fuzzy logic based high speed public-key cryptography (FLHSPKC) has been proposed by satisfying the major issues likes computational safety, power management and restrict...
EDAC: A Novel Energy-Aware Clustering Algorithm for Wireless Sensor Networks
Clustering is a useful technique for reducing energy consumption in wireless sensor networks (WSN). To achieve a better network lifetime performance, different clustering algorithms use various parameters for cluster hea...
Optimization Query Process of Mediators Interrogation Based On Combinatorial Storage
In the distributed environment where a query involves several heterogeneous sources, communication costs must be taken into consideration. In this paper we describe a query optimization approach using dynamic programming...
A Machine Vision System for Quality Inspection of Pine Nuts
Computers and artificial intelligence have penetrated in the food industry since last decade, for intellectual automatic processing and packaging in general, and in assisting for quality inspection of the food itself in...
A New Algorithm to Represent Texture Images
In recent times the spatial autoregressive models have been extensively used to represent images. In this paper we propose an algorithm to represent and reproduce texture images based on the estimation of spatial autoreg...