Algoritmos genéticos para o problema de programação de tarefas em máquinas paralelas idênticas com dois critérios
Resumo
Este artigo aborda o problema de escalonamento de tarefas em máquinas paralelas idênticas com tempos de preparação dependentes da seqüência. Este problema consiste em determinar a ordem de processamento de um conjunto de tarefas em um conjunto de máquinas, minimizando simultaneamente dois critérios: tempo de finalização do processamento das tarefas (makespan) e atraso total das tarefas com relação a suas datas de entrega. Este problema possui um conjunto de soluções denominadas Paretoótimas ou eficientes. O problema é resolvido aproximadamente usando três algoritmos genéticos diferentes que usam estratégias de busca local. Resultados computacionais mostram que os algoritmos genéticos apresentam um bom desempenho em termos de qualidade de soluções e tempo de execução.Referências
Armentano, V. A., Yamashita, D. S. (2000) Tabu Search for Schedulling on Identical Parallel Machines to Minimizing Mean Tardiness. Journal Of Intelligent Manufacturing. , Vol.11, No.5, p.453-460.
Armentano V.A. and Arroyo J.E.C., (2004) An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem. Journal of Heuristics. Vol. 10, No. 5, pp. 463-481.
Arroyo J.E.C. and Armentano V.A., (2005) A Genetic Local Search Algorithm for Multi-Objective Flowshop Scheduling Problems. European Journal of Operational Research, Vol. 167, No.3, pp. 717-738.
Bilge, U., Kirac, F., Kurtulan, M. and Pekgun, P., (2004) A tabu search algorithm for parallel machine total tardiness problem. Computers and Operations Research, Vol.31, No.3, pp. 397-414.
Cochran J. K., Horng S-M and Fowler J.W. (2003) A Multi-Population Genetic Algorithm to Solve Multi-Objective Scheduling problems for Parallel Machines. Comp & Operations Research, Vol.30 No.7 pp 1087-1102.
Czyzak P. and Jaszkiewicz A. (1998) Pareto Simulated Annealing – a metaheuristic technique for multiple objective combinatorial optimization, Journal of Multi-Criteria Decision Analysis, Vol. 7, pp. 34-47.
Deb, K.; Agrawal, S.; Pratab, A. & Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. KanGAL report 200001, Indian Institute of Technology, Kanpur, India.
Dileepan P. and Sen T. (1988) Bicriterion static scheduling research for a single machine, OMEGA, Vol. 16, pp. 53-59.
Ehrgott M. (2000) Approximation algorithms for combinatorial multicriteria optimization problems. International Transactions in Operational Research, Vol. 7, pp. 5-31.
Gandibleux, X. and Fréville, A. (2000). Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: The two objectives case. Journal of Heuristics, Vol. 6, pp.361-383.
Guinet, A., (1995) Scheduling Independent Jobs on Uniform Parallel Machines to Minimize Tardiness Criteria, Journal of Intelligent Manufacturing, Vol. 6, pp. 95-103.
Hansen, M.P. and Jaszkiewicz, A. (1998). Evaluating the quality of approximations to the nondominated set. Technical Report, Institute of Mathematical Modeling, Technical University of Denmark.
Ishibuchi, H. and Murata, T. (1998). A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man and Cybernetics-part C, Vol. 28, pp. 392-403.
Jaskiewicz, A. (2002). On the performance of multiple objective genetic local search on the 0/1 knapsack problem: A comparative experiment. IEE Transaction on Evolutionary Computation, Vol. 6, No 4, pp. 402-412.
Jones D.F., Mirrazavi S.K. and Tamiz M. (2002) Multi-objective meta-heuristics: An overview of the current state-of-art. European Journal of Operational Research, Vol.137, pp. 1-19.
Lee, Y.H., Bhaskaram, K. and Pinedo, M. (1997) A heuristic to minimize the total weighted tardiness with sequence-dependent setup times. IIE Transactions, Vol.29, No. 1, pp. 45-52.
Mendes, A., Müller, F., França P. and Moscato P. (2002) Comparing Meta-Heuristic Approaches for Parallel Machine Scheduling Problems, Production Planning & Control, Vol. 13, No. 2, pp. 143-154.
Michalewicz Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Thir Edition, Springer-Verlag Berlin Heidelberg New York.
Min, L. and Cheng, W. (1999) A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines, Artificial Intelligence in Engineering, Vol. 13, No. 4, pp.399-403.
Steuer, R.E. (1986), Multiple Criteria Optimization – Theory, Computation and Application. Wiley, New York.
Suresh V. and Chaudhuri D. (1996) Bicrteria Scheduling Problem for Unrelated Parallel Machines. Computers Ind. Engng, Vol. 130, No.1, pp. 77-82.
T’Kindt V. and Billaut J.C. (2001) Multicriteria Scheduling Problems: A Survey. RAIRO Operational Research , Vol. 35, pp. 143-163.
Armentano V.A. and Arroyo J.E.C., (2004) An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem. Journal of Heuristics. Vol. 10, No. 5, pp. 463-481.
Arroyo J.E.C. and Armentano V.A., (2005) A Genetic Local Search Algorithm for Multi-Objective Flowshop Scheduling Problems. European Journal of Operational Research, Vol. 167, No.3, pp. 717-738.
Bilge, U., Kirac, F., Kurtulan, M. and Pekgun, P., (2004) A tabu search algorithm for parallel machine total tardiness problem. Computers and Operations Research, Vol.31, No.3, pp. 397-414.
Cochran J. K., Horng S-M and Fowler J.W. (2003) A Multi-Population Genetic Algorithm to Solve Multi-Objective Scheduling problems for Parallel Machines. Comp & Operations Research, Vol.30 No.7 pp 1087-1102.
Czyzak P. and Jaszkiewicz A. (1998) Pareto Simulated Annealing – a metaheuristic technique for multiple objective combinatorial optimization, Journal of Multi-Criteria Decision Analysis, Vol. 7, pp. 34-47.
Deb, K.; Agrawal, S.; Pratab, A. & Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. KanGAL report 200001, Indian Institute of Technology, Kanpur, India.
Dileepan P. and Sen T. (1988) Bicriterion static scheduling research for a single machine, OMEGA, Vol. 16, pp. 53-59.
Ehrgott M. (2000) Approximation algorithms for combinatorial multicriteria optimization problems. International Transactions in Operational Research, Vol. 7, pp. 5-31.
Gandibleux, X. and Fréville, A. (2000). Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: The two objectives case. Journal of Heuristics, Vol. 6, pp.361-383.
Guinet, A., (1995) Scheduling Independent Jobs on Uniform Parallel Machines to Minimize Tardiness Criteria, Journal of Intelligent Manufacturing, Vol. 6, pp. 95-103.
Hansen, M.P. and Jaszkiewicz, A. (1998). Evaluating the quality of approximations to the nondominated set. Technical Report, Institute of Mathematical Modeling, Technical University of Denmark.
Ishibuchi, H. and Murata, T. (1998). A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man and Cybernetics-part C, Vol. 28, pp. 392-403.
Jaskiewicz, A. (2002). On the performance of multiple objective genetic local search on the 0/1 knapsack problem: A comparative experiment. IEE Transaction on Evolutionary Computation, Vol. 6, No 4, pp. 402-412.
Jones D.F., Mirrazavi S.K. and Tamiz M. (2002) Multi-objective meta-heuristics: An overview of the current state-of-art. European Journal of Operational Research, Vol.137, pp. 1-19.
Lee, Y.H., Bhaskaram, K. and Pinedo, M. (1997) A heuristic to minimize the total weighted tardiness with sequence-dependent setup times. IIE Transactions, Vol.29, No. 1, pp. 45-52.
Mendes, A., Müller, F., França P. and Moscato P. (2002) Comparing Meta-Heuristic Approaches for Parallel Machine Scheduling Problems, Production Planning & Control, Vol. 13, No. 2, pp. 143-154.
Michalewicz Z. (1996) Genetic Algorithms + Data Structures = Evolution Programs. Thir Edition, Springer-Verlag Berlin Heidelberg New York.
Min, L. and Cheng, W. (1999) A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines, Artificial Intelligence in Engineering, Vol. 13, No. 4, pp.399-403.
Steuer, R.E. (1986), Multiple Criteria Optimization – Theory, Computation and Application. Wiley, New York.
Suresh V. and Chaudhuri D. (1996) Bicrteria Scheduling Problem for Unrelated Parallel Machines. Computers Ind. Engng, Vol. 130, No.1, pp. 77-82.
T’Kindt V. and Billaut J.C. (2001) Multicriteria Scheduling Problems: A Survey. RAIRO Operational Research , Vol. 35, pp. 143-163.
Publicado
30/06/2007
Como Citar
ARROYO, José Elias Claudio; VIANNA, Dalessandro Soares.
Algoritmos genéticos para o problema de programação de tarefas em máquinas paralelas idênticas com dois critérios. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 6. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1538-1547.
ISSN 2763-9061.
