Plenary
Lecture
A Method for a Class of Scheduling Problems
Professor Nodari Vakhania
Science Faculty, State University of Morelos, Mexico
Inst. of Computational Math., Georgian Academy of
Sciences
Email: nodari@uaem.mx
Abstract:
Discrete (combinatorial) optimization problems are of a
significant practical interest. A set of constraints
specify feasible solutions, while a solution which
minimizes (maximizes) the given objective function is an
optimal one. Typically, we are looking for an optimal or
near to the optimal feasible solution. The set of the
feasible solutions is always finite, thus there is no
major difficulty from the mathematical point of view: we
just need to generate all the feasible solutions
determining one with the minimal (maximal) value of the
objective function. But this might be practically
impossible when the number of feasible solutions grows
exponentially with the length of the input.
Scheduling problems, with which we deal in this talk,
constitute a part of the combinatorial optimization
problems. They deal with a finite set of requests
(usually called tasks or jobs) which have to be
performed on a finite set of resources (usually called
machines or processors). A job in a factory or a program
in a computer system or a lesson in a school are
examples of requests. A machine in a factory or a
processor in a computer system or a teacher in a school
are examples of resources. Each request has its
processing requirement, i.e., it needs a prescribed time
on a resource, and usually a resource cannot handle more
than one request at a time (for example, a teacher
cannot give two lessons simultaneously). Besides, there
are a limited number of resources and time is also
limited, so that we need to arrange an order in which
the requests are handled by the resources to make the
total elapsed time as small as possible. We may have
different time objective functions (usually
nondecreasing), which we wish to minimize or maximize.
We may also have some additional restrictions on the
orderings which we admit (for example, some lessons
should be given before the others). Although the number
of all possible admissible orderings or the feasible
solutions is finite, it might be extremely large.
In this talk we will discuss a method that permits to
construct efficient direct combinatorial polynomialtime
algorithms for a class of scheduling problems in which
the jobs are released (become available) at different
time moments, whereas we wish to complete each job by a
specified time moment, the socalled duedate. Our
objective is to minimize a nondecreasing (time)
objective function. Using this method, we were able to
improve a number of existing algorithm and have solved
some earlier open problems. The method classiffies jobs
into exible and rigid ones. Intuitively, the exible jobs
are free to be moved easily without becoming late,
whereas the movement of the rigid jobs is quite
restricted. We show that the exible jobs need to be
distributed in between the rigid ones in a way that uses
the space inbetween different sequences of rigid jobs
in some optimal manner. In this way versions of a better
known bin backing problem arise. Our algorithms use
different strategy for finding such an optimal job
partition. Some of them construct it iteratively: a new
schedule, associated with a node in a search tree, is
generated at each iteration. These schedules are derived
from the neighborhood which we define. In other
algorithms, finding the above partition is considered as
an independent auxiliary problem.
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, Moscow in 1991, and the doctoral
degree in mathematical cybernetics at the Georgian
Academy of Sciences, Tbilisi in 2004. His main research
interests include design and analysis of algorithms,
computational complexity and scheduling theory. He is an
author of over 50 research papers. His articles were
published in Journal of Algorithms, Journal of
Combinatorial Optimization, Journal of Scheduling,
Journal of Computer and System Sciences, Annals of
Operations Research, Operations Research Letters, Naval
Research Logistics and other highranked international
journals. Professor Vakhania has been worked in
different scientific committees including those at
Mexican Science Foundation CONACyT. He has been a
referee of Journal of Algorithms, Journal of Scheduling,
Information Processing Letters, OMEGA, Computers &
Operations Research, Operations Research Letters and
other journals. He has obtained research grants in
Germany, France, The Netherlands, USA, Russia and Mexico
and had over 40 invited talks in di erent countries.
