Algoritmo para o problema de seqüenciamento em máquinas paralelas não-relacionadas
Algorithm to solve the unrelated parallel machine scheduling problem
Muller, Felipe Martins; Dias, Odon Bastos; Araújo, Olinto César B. de
http://dx.doi.org/10.1590/S0103-65132002000200002
Prod, vol.12, n2, p.6-17, 2002
Resumo
Este trabalho trata do problema de seqüenciamento de n tarefas independentes em m máquinas paralelas não-relacionadas com o objetivo de minimizar o tempo de execução da máquina mais carregada (makespan). É proposto um novo algoritmo de busca local em conexão com um esquema de vizinhança que usa estrutura de intervalos e o conceito de eficiência das máquinas para cada tarefa. O algoritmo proposto, denominado Mutat, é comparado com outros algoritmos para avaliar a qualidade das soluções obtidas. A nova abordagem encontra soluções que superam, em qualidade e tempo computacional, o melhor algoritmo de busca local encontrado na literatura para este problema.
Palavras-chave
Seqüenciamento, Máquinas não-relacionadas, Busca local, Heurísticas
Abstract
This work deals with the problem of scheduling n independent jobs on m unrelated parallel machines with the objective of minimizing the makespan (the total elapsed time from the start of execution until all jobs are completed). In this work we propose a new local search algorithm in connection with a powerful neighborhood scheme that uses a structure of intervals and uses the efficiency of the machines for each job. The proposed algorithm, called Mutat, is compared with other algorithms in order to evaluate the quality of the solutions obtained. The new approach finds solutions that overcome, in quality and computational time, the best algorithm of local search found in the literature for this problem.
Keywords
Scheduling, Unrelated machines, Local search, Heuristics
References
BAKER, K.R. Introduction to Sequencing and Scheduling. New York: John Wiley & Sons Inc., 1974.
CHO, Y.; SHANI, S. Bounds for list schedules on uniforms processors scheduling. SIAM Journal on Computing, Vol. 9, pp. 91-103, 1980.
COFFMAN Jr., E.G.; GAREY, M.R.; JOHNSON, D.S. An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, Vol. 7, pp. 1-17, 1978.
DOBSON, G. Scheduling independent tasks on uniforms processors. SIAM Journal on Computing, Vol. 13, pp. 705-716, 1984.
FINN, G.; HOROWITZ, E. A linear time approximation algorithm for multiprocessor scheduling. BIT, Vol. 19, pp. 312-320, 1979.
FRANÇA, P.M.; GENDREAU M.; LAPORTE G.; MÜLLER F.M. A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Computers Ops. Res. 21, pp.205-210, 1994.
FRIESEN, D.K.; LANGSTON, M.A. Bounds for MULTIFIT scheduling on uniform processors. SIAM Journal on Computing, Vol. 12, pp. 60-70, 1983.
FRIESEN, D.K.; LANGSTON, M.A. Evaluation of a MULTIFIT-based scheduling algorithm. Journal of Algorithms, Vol. 7, pp. 35-59, 1986.
GAREY, M.R.; JOHNSON, D.S. Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco : W. H. Freeman and Company, 1979.
GLASS, C.A.; POTTS, C.N.; SHADE, P. Unrelated parallel machine scheduling using local search, Mathl. Comput. Modelling 20 (2), pp 41-52.54, 1994.
GONZALEZ, T.; IBARRA, O.H.; SAHNI, S. Bounds for LPT scheduling on uniforms processors. SIAM Journal on Computing, Vol. 6, pp. 155-166, 1977.
GRAHAM, R.L. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, Vol. 17, pp. 416-429, 1969.
HOROWITZ, E.; SANHI, S.K. Exact and approximation algorithms for scheduling nonidentical processors. J. Assoc. Comput., Vol. 23, p. 317-327, 1976.
LANGSTON, M.A. Improved 0/1 interchange scheduling. BIT, Vol. 22, pp. 282-290, 1982.
LAWLER, E.L.; LENSTRA, J. K.; RINNOOY KAN, A.H.G.; SHMOYS, D.B. Sequencing and scheduling: algorithms and complexity, Report BS-R8909, Center for Mathematics and Computer Science, Amsterdan, 1989.
LIMBERGER, S.J. Algoritmos heurísticos e exatos para solução de problemas de seqüenciamento em processadores paralelos uniformes. Tese de Mestrado, Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal de Santa Maria, UFSM, 1997.
LIU, J. W. S.; LIU, C.L. Bounds on scheduling algorithms for heterogeneous computing system. Information Processing 74, pp. 349-353, 1974.
MARTELLO, S.; SOUMIS, F.; TOTH, P. Exact and approximation algorithms for makespan minimization on unrelated parallel machines. Discrete Applied Mathematics 75, pp. 169-188, 1997.
McNAUGHTON, R. Scheduling with deadlines and loss functions. Management Science, Vol. 6(1), pp. 1-12, 1959.
MÜLLER, F.M. Algoritmos heurísticos e exatos para resolução do problema de seqüenciamento em processadores paralelos. Tese de Doutorado, Faculdade de Engenharia elétrica, Universidade Estadual de Campinas. Campinas, 1993.
MÜLLER, F.M.; ARAÚJO, O.C.B. Neighbourhood Constraint for a Tabu Search Algorithm to Schedule Jobs on Unrelated Parallel Machines. 4th Metaheuristics International Conference, Porto-Portugal, pp. 551-555, 2001.
MÜLLER, F.M.; CAMOZZATO, M.M.; ARAÚJO, O. C. B. Exact Algorithms for the Imbalanced Time Minimizing Assignment Problem. Brazilian Symposium on Graphs, Algorithms and Combinatorics, Fortaleza-Brasil, pp. 172-175, 2001.
PIERSMA, N.; VAN DIJK, W. A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search. Mathl. Comput. Modelling 24 (9), pp. 11-19, 1996.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email