Siepak, Marcin
An exact algorithm for the uncertain version of parallel machines scheduling problem with the total completion time criterion
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 NPhard 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 = {5363},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783939897392},
ISSN = {21906807},
year = {2012},
volume = {22},
editor = {Stefan Ravizza and Penny Holborn},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3546},
URN = {urn:nbn:de:0030drops35469},
doi = {http://dx.doi.org/10.4230/OASIcs.SCOR.2012.53},
annote = {Keywords: Task scheduling, Interval uncertainty, Minmax regret, Branch and Bound},
note = {The research was supported by the Polish National Science Centre Grant DEC2011/01/N/ST6/01803.}
}
Keywords: 

Task scheduling, Interval uncertainty, Minmax regret, Branch and Bound 
Seminar: 

3rd Student Conference on Operational Research

Issue date: 

2012 
Date of publication: 

26.06.2012 