Email this article On complexity of optimal recombination for flowshop scheduling problems
- Authors: Kovalenko Y.V.1
-
Affiliations:
- Sobolev Institute of Mathematics
- Issue: Vol 10, No 2 (2016)
- Pages: 220-231
- Section: Article
- URL: https://bakhtiniada.ru/1990-4789/article/view/212336
- DOI: https://doi.org/10.1134/S1990478916020071
- ID: 212336
Cite item
Open Access
Access granted
Subscription Access
Abstract
Under study is the complexity of optimal recombination for various flowshop scheduling problems with the makespan criterion and the criterion of maximum lateness. The problems are proved to be NP-hard, and a solution algorithm is proposed. In the case of a flowshop problem on permutations, the algorithm is shown to have polynomial complexity for “almost all” pairs of parent solutions as the number of jobs tends to infinity.
About the authors
Yu. V. Kovalenko
Sobolev Institute of Mathematics
Author for correspondence.
Email: julia.kovalenko.ya@yandex.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090
Supplementary files
