Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/10029
Title: | A Giffler-Thompson genetic algorithm for the static job-shop scheduling problem | Authors: | Moonen, Mark JANSSENS, Gerrit K. |
Issue Date: | 2007 | Publisher: | Binary Information Press | Source: | Journal of Information and Computational Science, 4(2). p. 629-642 | Abstract: | As the job shop scheduling problem is a di±cult problem in combinatorial optimisation, a lot of research has been devoted to obtaining lower bounds for its objective function, in constructing branch-and-bound algorithms and in developing e±cient heuristics and meta-heuristics. Several genetic algorithms have been developed for the job-shop scheduling problem. The design of the genetic algorithms for the problem under study varies in the way of encoding a solution and in the use of its various operators. In this design of the genetic algorithm a crossover operator is developed based on principles set by Gi²er and Thompson to generate active schedules. Two alternative designs are tested on a number of benchmark problems. While performing well in general, the genetic algorithm performs rather poor on benchmark problems, which are known in the literature as extremely hard to solve. The genetic algorithm, as presented here, makes use of a parameter, which is believed to have an important influence on performance of the algorithm and of which an intelligent setting of its value might lead to promising results for the most di±cult job-shop scheduling problems. | Keywords: | Job-shop scheduling; Static; Genetic algorithm | Document URI: | http://hdl.handle.net/1942/10029 | ISSN: | 1548-7741 | Category: | A2 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
problem.pdf | Peer-reviewed author version | 278.51 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.