An Efficient Heuristic for a Discrete Optimization Problem

Authors

  • Nodari Vakhania Centro de Investigación en Ciencias, UAEMor
  • Elisa Chinos Centro de Investigación en Ciencias, UAEMor
  • Crispin Zavala Centro de Investigación en Ciencias, UAEMor

Keywords:

Discrete optimization, Feasible solution, Scheduling, Heuristic, Approximation algorithm

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.

Downloads

Published

2016-01-05

Issue

Vol. 2 No. 2 (2015)

Section

Articles

License

Policy for Journals/Articles with Open Access

Authors who publish with this journal agree to the following terms:
    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  1. Authors are permitted and encouraged to post links to their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work

Policy for Journals / Manuscript with Paid Access

Authors who publish with this journal agree to the following terms:
    1. Publisher retain copyright .

  1. Authors are permitted and encouraged to post links to their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work .