An exact algorithm for the uncertain version of parallel machines scheduling problem with the total completion time criterion

Author Marcin Siepak



PDF
Thumbnail PDF

File

OASIcs.SCOR.2012.53.pdf
  • Filesize: 438 kB
  • 11 pages

Document Identifiers

Author Details

Marcin Siepak

Cite AsGet BibTex

Marcin Siepak. An exact algorithm for the uncertain version of parallel machines scheduling problem with the total completion time criterion. In 3rd Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 22, pp. 53-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/OASIcs.SCOR.2012.53

Abstract

An uncertain version of parallel and identical machines scheduling problem with total completion time criterion is considered. It is assumed that the execution times of tasks are not known a priori but they belong to the intervals of known bounds. The absolute regret based approach for coping with such an uncertainty is applied. This problem is known to be NP-hard and a branch and bound algorithm (B&B) for finding the exact solution is developed. The results of computational experiments show that for the tested instances of the uncertain problem — B&B works significantly faster than the exact procedure based on enumeration of all the solutions. The algorithm proposed has application for further research of quality evaluation for heuristic and approximate solution approaches for the considered problem (in order to check how far from the optimality are solutions generated by them) and also in the cases where the requirement is to obtain the exact solutions for the uncertain problem.
Keywords
  • Task scheduling
  • Interval uncertainty
  • Minmax regret
  • Branch and Bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail