Novos Algoritmos para o Problema de Sequenciamento em M aquinas Paralelas N~ ao-Relacionadas com

Content Provider	Semantic Scholar
Author	Perdig, Luciano
Copyright Year	2014
Abstract	This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times – UPMSPST, having as goal to minimize the makespan. In order to solve it, three heuristic algorithms and a hybrid algorithm were developed. The first heuristic algorithm, called HIVP, has an initial solution generated by a greedy constructive procedure based on the Heuristic-Biased Stochastic Sampling and on the Adaptive Shortest Processing Time – ASPT rule. This solution is then refined by the Iterated Local Search – ILS procedure, having the Random Variable Neighborhood Descent as local search method. Moreover, the search is periodically intensified and diversified by a Path Relinking – PR procedure. In the second algorithm, called GIAP, the initial solution is created by a procedure inspired on the Greedy Randomized Adaptive Search Procedures. This solution is then refined by an ILS procedure that uses the procedure Adaptive Local Search – ALS as local search method. The search is also intensified and diversified by a PR procedure. The third and final heuristic algorithm, called AIRP, has its initial solution generated by a greedy constructive procedure based on ASPT rule. This solution is then refined by the ILS, having as local search a procedure called RVI. Analogously to the previous algorithms, the search also applies periodically an intensification and diversification strategy based on the PR procedure. The hybrid algorithm, named AIRMP, is similar to the AIRP heuristic algorithm, differing from it by adding a module of mixed integer linear programming. To apply this module one pair of machines are selected and subsets of jobs of these machines. These subsets are combined and they pass through a local search that consists in running a mathematical programming solver applied to the best formulation among the studied and developed ones. By computational experiments it was concluded that the AIRP algorithm obtained the best results among the proposed heuristic algorithms, outperforming several other algorithms from the literature. Experiments were also conducted to compare the AIRMP and AIRP algorithms. As the AIRMP needs more time to execute the mathematical programming module, these
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www.repositorio.ufop.br/bitstream/123456789/4220/1/DISSERTA%C3%87%C3%82O_NovosAlgoritimos.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article