License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SCOR.2012.53
URN: urn:nbn:de:0030-drops-35469
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3546/
Go to the corresponding OASIcs Volume Portal

Siepak, Marcin

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

pdf-format:
7.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{siepak:OASIcs:2012:3546,
  author =	{Marcin Siepak},
  title =	{{An exact algorithm for the uncertain version of parallel machines scheduling problem with the total completion time criterion}},
  booktitle =	{3rd Student Conference on Operational Research},
  pages =	{53--63},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Stefan Ravizza and Penny Holborn},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3546},
  URN =		{urn:nbn:de:0030-drops-35469},
  doi =		{10.4230/OASIcs.SCOR.2012.53},
  annote =	{Keywords: Task scheduling, Interval uncertainty, Minmax regret, Branch and Bound}
}

Keywords: Task scheduling, Interval uncertainty, Minmax regret, Branch and Bound
Collection: 3rd Student Conference on Operational Research
Issue Date: 2012
Date of publication: 26.06.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI