10.14489/vkit.2016.04.pp.011-015

DOI: 10.14489/vkit.2016.04.pp.011-015

Матренин П. В., Манусов В. З.
АДАПТИВНЫЙ АЛГОРИТМ РОЯ ЧАСТИЦ В ЗАДАЧАХ ОПЕРАТИВНОГО ПЛАНИРОВАНИЯ
(c.011-015)

Аннотация. Проведено исследование алгоритма роя частиц для решения задач оперативного календарного планирования. Показана эффективность предложенного подхода на тестовых задачах календарного планирования класса job-shop. Определена важность адаптации параметров алгоритма роя частиц к условиям решаемых задач оптимизации и высокую эффективность рассмотрен-ного подхода для задач оперативного календарного планирования.

Ключевые слова: алгоритм роя частиц; генетический алгоритм; адаптация; календарное планирование; комбинаторная оптимизация.

Matrenin P. V., Manusov V. Z.
ADAPTIVE PARTICLE SWARM OPTIMIZATION FOR THE OPERATIONAL SCHEDULING PROBLEM
(pp.011-015)

Abstract. The article describes a study of the Particle Swarm Optimization algorithm for solving the operational scheduling problem. A feature of such problems is the high computational complexity; the multifactorial; the need for rapid obtain the satisfactory solutions. Since the effectiveness of the Particle Swarm Optimization algorithm depends on the values of the parameters used by it, then a restriction of the particles’ velocity and an evolutionary meta-optimization were applied to improve the efficiency of the algorithm. The meta-optimization was implemented basing on the Genetic algorithm, and the parameter selection of the Particle Swarm Optimization algorithm was performed on only three problems, then these parameters were tested on other similar tasks. The effectiveness of the proposed approach was shown using a number of test job-shop scheduling problems. The study has proven the importance of adapting the parameters of the Particle Swarm Optimization algorithm to conditions of optimization problems and high efficiency of this approach for the operational scheduling problems.

Keywords: Particle Swarm Optimization; Genetic algorithm; Adaptation; Scheduling problem; Combinatorial optimization.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

П. В. Матренин, В. З. Манусов (Новосибирский государственный технический университет) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

P. V. Matrenin, V. Z. Manusov (Novosibirsk State Technical University) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Kennedy J., Eberhart R. Particle Swarm Optimization // IEEE Intern. Conf. on Neural Network. 1995. V. 5, № 3. Р. 1942 – 1948.
2. Wolpert D. H., Macready W. G. No Free Lunch Theorems for Optimization // IEEE Transactions on Evolutionary Computation. 1997. V. 1, № 1. Р. 67 – 82.
3. Pedersen M., Chippereld A. Simplifying Particle Swarm Optimization // Applied Soft Computing. 2010. V. 10, № 2. Р. 618 – 628.
4. Shi Y., Eberhart R. C. Parameter Selection in Particle Swarm Optimization // Proc. of the 7th Intern. Conf. on Evolutionary Programming VII (EP98). San Diego, CA, USA, 25 – 27 March 1998. San Diego, 1998. Р. 591 – 600.
5. Garey M., Johnson D., Sethy R. The Complexity of Flow Shop and Job Shop Scheduling // Mathematics of Opera-tions Research. 1976. № 1. Р. 117 – 129.
6. Pezzella F., Merelli E. A Tabu Search Method Guided by Shifting Bottleneck for the Job Shop Scheduling Problem // European Journal of Operational Research. 2000. № 120. Р. 297 – 310.
7. Pedersen M. Good Parameters for Particle Swarm Optimi-zation // Hvass Laboratories Technical Report no. HL1001. 2010. 12 р.
8. Fan H. A Modification to Particle Swarm Optimization Algorithm // Engineering Computations: International Journal for Computer-Aided Engineering. 2002. № 19. Р. 970 – 989.
9. Матренин П. В., Секаев В. Г. Адаптивный алгоритм муравьиной колонии при построении и оптимизации расписаний // Вестник компьютерных информационных технологий. 2012. № 11. С. 19 – 24.
10. Beasley J. E. OR-Library: Distributing Test Problems by Electronic Mail // Journal of the Operational Research Society. 1990. № 41(11). Р. 1069 – 1072.
11. Eberhart R. C., Shi Y. Particle Swarm Optimization: Developments, Applications and Resources // IEEE Congress on Evolutionary Computation. Seoul, Korea, 27 – 29 May 2001. Seul, 2001. V. 1. Р. 81 – 86.

Eng

1. Kennedy J., Eberhart R. (1995). Particle swarm optimiza-tion. IEEE International Conference on Neural Network, 5(3), pp. 1942-1948.
2. Wolpert D. H., Macready W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), pp. 67-82.
3. Pedersen M., Chippereld A. (2010). Simplifying particle swarm optimization. Applied Soft Computing, 10(2), pp. 618-628. doi: 10.1016/j.asoc.2009.08.029
4. Shi Y., Eberhart R. C. (1998). Parameter selection in par-ticle swarm optimization. Proc. of the 7th International Conference on Evolutionary Programming VII (EP98). San Diego, CA, USA, 25 – 27 March 1998, pp. 591-600.
5. Garey M., Johnson D., Sethy R. (1976). The complexity of flow shop and job shop scheduling. Mathematics of Operations Research, (1), pp. 117-129.
6. Pezzella F., Merelli E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem.European Journal of Operational Research, 120, pp. 297-310.
7. Pedersen M. (2010). Good parameters for particle swarm optimization. Hvass Laboratories Technical Report no. HL1001. 2010.
8. Fan H. A. (2002). Modification to particle swarm optimi-zation algorithm. Engineering Computations: International Journal for Computer-Aided Engineering, 19, pp. 970-989. doi: 10.1108/02644400210450378
9. Matrenin P. V., Sekaev V. G. (2012). Adaptive algorithm of the ant colony at construction and optimization of schedules. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (11), pp. 19-24.
10. Beasley J. E. (1990). OR-library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), pp. 1069-1072.
11. Eberhart R. C., Shi Y. (2001). Particle swarm optimiza-tion: developments, applications and resources. IEEE Congress on Evolutionary Computation. Seoul, Korea, 27 – 29 May 2001, Vol. 1, pp. 81-86.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2016.04.pp.011-015}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2016.04.pp.011-015}