DROPS

Document

DOI: 10.4230/OASIcs.SCOR.2012.53

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

Authors: Marcin Siepak

Published in: OASIcs, Volume 22, 3rd Student Conference on Operational Research (2012)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{siepak:OASIcs.SCOR.2012.53,
  author =	{Siepak, Marcin},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Ravizza, Stefan and Holborn, Penny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2012.53},
  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}
}

Search Results

Documents authored by Siepak, Marcin

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

Abstract

Cite as

Thanks for your feedback!

Could not send message