Production Scheduling Approaches
Read these sections, which highlight key problems in production scheduling. How can job sequencing and priority rules help to alleviate the key problems? Can you identify the different rules that affect job sequencing and priority rules in operations management?
4. Meta-heuristics for solving the JSSP
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 papers. Scheduling has been faced from many perspectives, using formulations and tools of various disciplines such as control theory, physical science, and artificial intelligence systems. 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 environment. 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 outstanding.
Guidelines in using heuristics in combinatorial optimization can be found in Hertz. A classification of heuristic methods was proposed by Zanakis et al.. 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 problem. 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 basis.
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. The meta-heuristics
The term metaheuristics was introduced by F. Glover in the paper about Tabu search, and in general the heuristics, do not ensure optimal results but they usually tend to work well. 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 Annealing and Electromagnetic like Methods, biology (Genetic Algorithms, Tabu Search) and ethnology (Ant Colony, Bees Algorithm), human science (Neural Networks), they are generally of discrete origin but can be adapted to the other types of problems.