Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.1/1154
Título: Optimised search heuristics: combining metaheuristics and exact methods to solve scheduling problems
Autor: Fernandes, Susana
Orientador: Lourenço, Helena Ramalhinho
Palavras-chave: Metaheuristics
Exact Algorithms
GRASP
Tabu Search
Branch-and-Bound
Valid Inequalities
Scheduling Problems
Data de Defesa: 2008
Resumo: Scheduling problems have many real life applications, from automotive industry to air traffic control. These problems are defined by the need of processing a set of jobs on a shared set of resources. For most scheduling problems there is no known deterministic procedure that can solve them in polynomial time. This is the reason why researchers study methods that can provide a good solution in a reasonable amount of time. Much attention was given to the mathematical formulation of scheduling problems and the algebraic characterisation of the space of feasible solutions when exact algorithms were being developed; but exact methods proved inefficient to solve real sized instances. Local search based heuristics were developed that managed to quickly find good solutions, starting from feasible solutions produced by constructive heuristics. Local search algorithms have the disadvantage of stopping at the first local optimum they find when searching the feasible region. Research evolved to the design of metaheuristics, procedures that guide the search beyond the entrapment of local optima. Recently a new class of hybrid procedures, that combine local search based (meta) heuristics and exact algorithms of the operations research field, have been designed to find solutions for combinatorial optimisation problems, scheduling problems included. In this thesis we study the algebraic structure of scheduling problems; we address the existent hybrid procedures that combine exact methods with metaheuristics and produce a mapping of type of combination versus application and finally we develop new innovative metaheuristics and apply them to solve scheduling problems. These new methods developed include some combinatorial optimisation algorithms as components to guide the search in the solution space using the knowledge of the algebraic structure of the problem being solved. Namely we develop two new methods: a simple method that combines a GRASP procedure with a branch-and-bound algorithm; and a more elaborated procedure that combines the verification of the violation of valid inequalities with a tabu search. We focus on the job-shop scheduling problem.
Descrição: Tese dout., Matemática, Investigação Operacional, Universidade do Algarve, 2009
Peer review: yes
URI: http://hdl.handle.net/10400.1/1154
Aparece nas colecções:FCT1-Teses
UA01-Teses

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
PhDThesis_SusanaFernandes.pdf1,42 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.