Heuristic algorithms for the problem of task scheduling with moving executors

• Autorzy: Józefczyk J.
• Języki publikacji: EN

Abstrakty

EN

New heuristic algorithms for solving the task scheduling problem with moving executors to minimize the sum of completion times are considered. The corresponding combinatorial optimization problem is formulated for single executor. A hybrid solution algorithm is introduced and investigated, where evolutionary as well as simulated annealing procedures are applied. A simulated annealing algorithm assists the evolutionary algorithm in three different ways. It is used for the generation of the initial set of solutions of the evolutionary algorithm. Moreover, this algorithm attempts to enhance the best solutions at current iterations of the evolutionary procedure. The results of the evaluation of the solution algorithms, which have been performed during the computer simulation experiments, are presented. The influence of the parameters of the solution algorithm as well as the task scheduling problem on the quality of results and on the time of computation is investigated.

Słowa kluczowe

EN

heuristic algorithm; evolutionary computation; evolutionary algorithm; task scheduling; artificial intelligence; combinatorial mathematics; combinatorial optimization problem

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2004
• Tom: Vol. 30, no 3
• Strony: 95--103
• Opis fizyczny: Bibliogr. 11 poz., wykr.

Twórcy

autor

Józefczyk J.

• Systems Research Institute of Polish Academy of Sciences, Laboratory of Knowledge Systems and Artificial Intelligence, Podwale St. 75, 50-449 Wrocław, Poland

Bibliografia

• [1] Averbakh O., Berman A., A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems. Operations Research, Vol. 47, 1999, 165-170.
• [2] Grefenstette J. et al, Genetic algorithms for the traveling salesman problem. Proceedings of International Conerence on Genetic Algorithms, Lawrence Erlbaum Associates, Mahaw NJ, USA, 1985.
• [3] Józefczyk J., Tasks scheduling on moving executors in complex operation system, Wrocław University of Technology Press, Wrocław 1996, (in Polish),
• [4] Józefczyk J., An algorithm for scheduling tasks on moving executors in complex operation systems, Proceedings of 1st IFAC Workshop on Manufacturing Systems MIM'97, Wien, Austria, 1997, 139-144.
• [5] Józefczyk J., Scheduling tasks on moving executors to minimise the maximum lateness, European Journal of Operational Research, Vol. 131, 2001, 171-187.
• [6] Józefczyk J., Application of genetic algorithms for solving the scheduling problem with moving executors. Systems Science, Vol. 27, 2001, 87-95.
• [7] Józefczyk J., Solving of the scheduling problem with moving executors using advanced genetic algorithms. Proceedings of 3rd Symposium AI Meth, Gliwice, Poland, 2002, 205-208.
• [8] Józefczyk J., On the application of evolutionary algorithms with multiple crossovers for solving the task scheduling problem. Proceedings of lASTED International Conference on Intelligent Systems and Control, Salzburg, Austria, Acta Press (Ed. M. H. Hamza) 2003, 301-306.
• [9] Józefczyk J., Scheduling of tasks on moving executors using advanced evolutionary algorithms. Proceedings of 16th International Conference on Systems Engineering, Vol. 1, Coventry, U.K., 2003, 309-314.
• [10] Józefczyk J., Hybrid solution algorithms for task scheduling problem with moving executors. Proceedings of 2nd IFAC Workshop on Advanced Fuzzy/Neural Control, Oulu, Finland, 2004, (accepted for the workshop).
• [11] Weinberg M., Oppacher F., A linear time algorithm for determining population diversity in evolutionary computation. Proceedings of lASTED International Conference on Intelligent Systems and Control, Salzburg, Austria, Acta Press (Ed. M. H. Hamza), 2003, 270-275.