Volume 23, No 2, 2016, P. 41-62

UDC 519.8
Yu. V. Kovalenko
On complexity of optimal recombination for flowshop scheduling problems

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.
Ill. 4, bibliogr. 26.

Keywords: flowshop problem, permutation, genetic algorithm, optimal recombination.

DOI: 10.17377/daio.2016.23.524

Yulia V. Kovalenko ¹
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: julia.kovalenko.ya@yandex.ru

Received 21 January 2016
Revised 11 February 2016

References

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.

[2] A. V. Eremeev and Yu. V. Kovalenko, On scheduling with technology based machines grouping, Diskretn. Anal. Issled. Oper., 18, No. 5, 54–79, 2011.

[3] A. V. Eremeev and Yu. V. Kovalenko, On complexity of optimal recombination for one scheduling problem with setup times, Diskretn. Anal. Issled. Oper., 19, No. 3, 13–26, 2012.

[4] R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of Scheduling, Addison-Wesley, Reading, MA, USA, 1967. Translated under the title Teoriya raspisanii, Nauka, Moscow, 1975.

[5] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. Translated under the title Algoritmy: postroenie i analiz, MTsNMO, Moscow, 2001.

[6] D. Rutkowska, M. Pilinski, and L. Rutkowski, Neural Networks, Genetic Algorithms and Fuzzy Systems, Naukowe PWN, Warsaw, 1997 [Polish]. Translated under the title Neironnye seti, geneticheskie algoritmy i nechyotkie sistemy, Goryachaya liniya–Telekom, Moscow, 2006.

[7] A. I. Serdyukov, On travelling salesman problem with prohibitions, in Upravlyaemye sistemy (Controlled Systems), Vol. 17, pp. 80–86, Inst. Mat. SO AN SSSR, Novosibirsk, 1978.

[8] V. S. Tanaev, Yu. N. Sotskov, and V. A. Strusevich, Teoriya raspisanii. Mnogostadiinye sistemy (Theory of Scheduling. Multi-Stage Systems), Nauka, Moscow, 1989.

[9] E. Balas and W. Niehaus, Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems, J. Heuristics, 4, No. 2, 107–122, 1998.

[10] B.-W. Cheng and C.-L. Chang, A study on flowshop scheduling problem combining Taguchi experimental design and genetic algorithm, Expert Syst. Appl., 32, No. 2, 415–421, 2007.

[11] V. Chvátal, Probabilistic methods in graph theory, Ann. Oper. Res., 1, No. 3, 171–182, 1984.

[12] W. Cook and P. Seymour, Tour merging via branch-decomposition, INFORMS J. Comput., 15, No. 3, 233–248, 2003.

[13] C. Cotta, E. Alba, and J. M. Troya, Utilizing dynastically optimal forma recombination in hybrid genetic algorithms, in Parallel Problem Solving from Nature — PPSN V (Proc. 5th Int. Conf. PPSN, Amsterdam, The Netherlands, Sept. 27–30, 1998), pp. 305–314, Springer, Heidelberg, 1998 (Lect. Notes Comput. Sci., Vol. 1498).

[14] C. Cotta and J. M. Troya, Genetic forma recombination in permutation flowshop problems, Evol. Comput., 6, No. 1, 25–44, 1998.

[15] A. V. Eremeev, On complexity of optimal recombination for binary representations of solutions, Evol. Comput., 16, No. 1, 127–147, 2008.

[16] A. V. Eremeev and Ju. V. Kovalenko, Optimal recombination in genetic algorithms for combinatorial optimization problems: Part I, Yugoslav J. Oper. Res., 24, No. 1, 1–20, 2014.

[17] A. V. Eremeev and Ju. V. Kovalenko, Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II, Yugoslav J. Oper. Res., 24, No. 2, 165–186, 2014.

[18] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, in Discrete Optimization II, pp. 287–326, North-Holland, Amsterdam, 1979 (Ann. Discrete Math., Vol. 5).

[19] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

[20] M. S. Nagano, R. Ruiz, and L. A. N. Lorena, A constructive genetic algorithm for permutation flowshop scheduling, Comput. Ind. Eng., 55, No. 1, 195–207, 2008.

[21] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice Hall, Upper Saddle River, USA, 2002.

[22] N. J. Radcliffe, The algebra of genetic algorithms, Ann. Math. Artif. Intell., 10, No. 4, 339–384, 1994.

[23] R. Tinós, D. Whitley, and G. Ochoa, Generalized asymmetric partition crossover (GAPX) for the asymmetric TSP, in Proc. 2014 Annual Conf. Genetic Evol. Comput., Vancouver, Canada, July 12–16, 2014, pp. 501–508, ACM, New York, 2014.

[24] M. Yagiura and T. Ibaraki, The use of dynamic programming in genetic algorithms for permutation problems, Eur. J. Oper. Res., 92, No. 2, 387–401, 1996.

[25] L. Wang and L. Zhang, Determining optimal combination of genetic operators for flow shop scheduling, Int. J. Adv. Manuf. Technol., 30, No. 3–4, 302–308, 2006.

[26] L. Zhang, L.Wang, and D.-Z. Zheng, An adaptive genetic algorithm with multiple operators for flowshop scheduling, Int. J. Adv. Manuf. Technol., 27, No. 5–6, 580–587, 2006.