|
Journal of Computer Science Technology Updates (Volume 2 Issue 2)
|
| An efficient Heuristic for a discrete optimization problem |
 |
Pages 38-45
Nodari Vakhania, Elisa Chinos and Crispin Zavala
DOI: http://dx.doi.org/10.15379/2410-2938.2015.02.02.05
Published: 05 January 2016 |
| Abstract |
| In this paper we deal with a discrete optimization problem, which, among many other such problems, is computationally intractable. Since the existence of an exact solution algorithm for our problem is highly unlikely, the development of heuristic and approximation algorithms is of a great importance. Here we briefly discuss this issue and describe a robust 2-approximation heuristic that is used for getting an approximation solution for the problem of scheduling jobs with release times and due-dates on a single machine to minimize the maximum job lateness. |
| Keywords |
| discrete optimization, feasible solution, scheduling, Heuristic, approximation algorithm. |
 |