Title :
Lower and upper bounds for the job shop scheduling problem with min-sum criteria
Author :
Benziani, Y. ; Kacem, Imed ; Laroche, Pierre ; Nagih, Anass
Author_Institution :
LCOMS, Univ. de Lorraine, Metz, France
Abstract :
The Job Shop Scheduling Problem is one of the most intractable NP-Hard combinatorial optimization problems. To solve optimally this problem in a reasonable computational time, we have to improve the lower and the upper bounds. In this paper we introduce a new lower bound to the job shop scheduling problem with min-sum criteria and compare two different genetic algorithms. The gap is computed by comparing the best upper bound with the lower bound.
Keywords :
combinatorial mathematics; computational complexity; genetic algorithms; job shop scheduling; NP-hard combinatorial optimization problems; computational time; genetic algorithms; job shop scheduling problem; lower bounds; min-sum criteria; upper bounds; Biological cells; Genetic algorithms; Job shop scheduling; Processor scheduling; Sociology; Statistics; Upper bound; Genetic Algorithm; Job Shop; Lower Bound; Min-Sum Criteria;
Conference_Titel :
Control, Decision and Information Technologies (CoDIT), 2013 International Conference on
Conference_Location :
Hammamet
Print_ISBN :
978-1-4673-5547-6
DOI :
10.1109/CoDIT.2013.6689653
