|
Diskretnyi Analiz i Issledovanie Operatsii, 2012, Volume 19, Issue 3, Pages 13–26
(Mi da687)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
On complexity of optimal recombination for one scheduling problem with setup times
A. V. Eremeeva, Yu. V. Kovalenkob a Omsk department of S. L. Sobolev Institute of Mathematics, SB RAS, Omsk, Russia
b Dostoevsky Omsk State University, Omsk, Russia
Abstract:
Computational complexity of optimal recombination for one scheduling problem with setup times is considered. Strong NP-hardness of this optimal recombination problem is proven and an algorithm for its solution is proposed. The algorithm is shown to be polynomial for “almost all” instances of the optimal recombination problem. Ill. 2, bibliogr. 19.
Keywords:
scheduling, setup time, genetic algorithm, optimal recombination.
Received: 19.07.2011 Revised: 17.11.2011
Citation:
A. V. Eremeev, Yu. V. Kovalenko, “On complexity of optimal recombination for one scheduling problem with setup times”, Diskretn. Anal. Issled. Oper., 19:3 (2012), 13–26
Linking options:
https://www.mathnet.ru/eng/da687 https://www.mathnet.ru/eng/da/v19/i3/p13
|
Statistics & downloads: |
Abstract page: | 312 | Full-text PDF : | 86 | References: | 39 | First page: | 4 |
|