Plenary Lecture

Efficient Heuristics for Discrete Optimization Problems

Professor Nodari Vakhania
Centro de Investigacion en Ciencias (UAEMor)

Abstract: Combinatorial optimization (CO) problems constitute a significant class of practical problems with a discrete nature. They have emerged in late 40-s of 20th century. With a rapid grow of the industry, the new demands in the optimal solution of the newly emerged resource management and distribution problems have arisen. For the development of effective solution methods, these problems were formalized and addressed mathematically. The CO problems are partitioned into two basic types, type P, which are polynomially solvable ones, and intractable NP-hard problems. Tt is believed that it’s very unlikely that an NP-hard problem can be solved in polynomial time. Hence, fast approximation algorithms are of a great demand. Greedy (heuristic) algorithms are efficient polynomial-time algorithms that create a feasible schedule. In this talk we shall discuss about the importance of heuristic solution methods for NP-hard optimization problems. Although all heuristic methods are fast, the quality of the solution that they deliver may vary a lot. Hence, heuristic algorithms with a good performance guarantee are of a primary interest. The scheduling problems constitute an important class of the discrete optimization problems. They deal with a finite set of requests called jobs to be performed (or scheduled) on a finite (and limited) set of resources called machines (or processors). The aim is to choose the order of processing the jobs on machines so as to meet a given objective criteria. A basic 2-approximation heuristic was suggested by Jackson in early 50s last century for scheduling jobs with release times and due-dates to minimize the maximum job lateness. The theoretical worst-case bound of 2 helps a little in practice, when the solution quality is important. The quality of the solution delivered by Jackson’s heuristic is closely related with the maximum job processing time pmax that occurs in a given problem instance and with the resultant interference with other jobs that such a long job may cause. We will show how the relationship of pmax with the optimal objective value can be used to obtain more accurate approximation ratio. As it was demonstrated in practice, by the computational experiments, the derived estimation may drastically outperform the worst-case ratio of 2.

Brief Biography of the Speaker: Nodari Vakhania is a titular professor at the Science Faculty, the State University of Morelos, Mexico and at the Institute of Computational Mathematics of the Georgian Academy of Sciences. He has received his Ph.D. degree in mathematical cybernetics at the Russian Academy of Sciences in 1991, and the doctoral degree (habilitation) in mathematical cybernetics at the Georgian Academy of Sciences in 2004. His main research interests include design and analysis of algorithms, discrete optimization, computational complexity and scheduling theory. He is an author of over 60 refereed research papers. His articles were published in Journal of Algorithms, Journal of Scheduling, Journal of Computer and System Sciences, Annals of Operations Research, Operations Research Letters, Naval Research Logistics, Theoretical Computer Science, International Journal of Production Research and other high-ranked international journals. Professor Vakhania has been worked in different scientific committees including those at Mexican Science Foundation CONACyT. He is an editor of Advances in Pure Math., Int. J. of Advanced Math. Sciences, Scientific World Journal, and a referee of Journal of Algorithms, Journal of Scheduling, Information Processing Letters, OMEGA, Computers & Operations Research, Operations Research Letters, Int. J. of Applied Intelligence, Mathematics of Operations Research and others. He has obtained research grants and honors in Germany, France, The Netherlands, USA, Russia and Mexico and had over 40 invited talks throughout the world.