DefinePK

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.