A logic has to be implemented in order to translate the scheduling problem into an algorithm structure. Academic researches on scheduling problems have produced countless papers1. Scheduling has been faced from many perspectives, using formulations and tools of various disciplines such as control theory, physical science and artificial intelligence systems2. Criteria for optimization could be ranked from applying simple priority rules to determine which job has to be processed next at the work-centres (i.e., dispatching) to the use of advanced optimizing methods that try to maximize the performance of the given environment3. Their way to solution is generally approximate – heuristics – but it constitutes promising alternatives to the exact methods and becomes the only one possible when dimension and/or complexity of the problem is outstanding4 .
Guidelines in using heuristics in combinatorial optimization can be found in Hertz (2003) 5. A classification of heuristic methods was proposed by Zanakis et al. (1989) 6. Heuristics are generally classified into constructive heuristics and improvement heuristics. The first ones are focused on producing a solution based on an initial proposal, the goal is to decrease the solution until all the jobs are assigned to a machine, not considering the size of the problem7. The second ones are iterative algorithms which explore solutions by moving step by step form one solution to another. The method starts with an arbitrary solution and transits from one solution to another according to a series of basic modifications defined on case by case basis8.
Relatively simple rules in guiding heuristic, with exploitation and exploration, are capable to produce better quality solutions than other algorithms from the literature for some classes of instances. These variants originate the class of meta-heuristic approaches 9. The meta-heuristics10- , and in general the heuristics, do not ensure optimal results but they usually tend to work well11. The purpose of the paper is to illustrate the most promising optimization methods for the JSSP.
As optimization techniques, metaheuristics are stochastic algorithms aiming to solve a broad range of hard optimization problems, for which one does not know more effective traditional methods. Often inspired by analogies with reality, such as physics science, Simulated Annealing12 and Electromagnetic like Methods13, biology (Genetic Algorithms 14, Tabu Search 15) and ethnology (Ant Colony16, Bees Algorithm17), human science (Neural Networks18), they are generally of discrete origin but can be adapted to the other types of problems.
- 1620 reads
