Dear Subhi,
I found your name in the CNII ASU GA blog.
My name is Ilya Gertsbakh, I worked on AEROFLOT flight scheduling (raspisanie)
In the period 1965-1972, under the guidance of Khaim Borisovich Kordonsky.
I wrote a short memo about the history of doing aviation schedule, in English,
and I would like to ask you to print it your blog.
Be in touch,
Ilya Gertsbakh
12.01.2017
-------------
Илья Борисович, приветствую Вас!
Замечательно, что Вы решили поделиться воспоминаниями, уверен, что они будут интересны (мне точно).
Я начал работать в НВЦ в 1967, благодаря Х.Б.Кордонскому, и прекрасно помню Вас.
С уважением
Subhi Gasanov
-------------
Dear Subhi,
Here it is. Working in CNII in 1965-72 was probably the most interesting period of my professional life.
It is sad that Khaim Borisovich, Misha Maksim and Valery Venevcev , the real authors and creators of the Aeroflot schedule,
are not with us anymore.
About myself: in 1974 I repatriated to Israel, worked in Ben Gurion University, Beersheva, in Mathematics Department, 1974-1999.
Since 1999 I am retired professor (called "emeritus"), live in Tel-Aviv, near the sea, and trying to do some science.
Presently working on network reliability.
Reading your blog with interest, would welcome any information exchange.
Privet vsem collegam, vsem kogo znaju lichno i pomnju a takzhe vsem ostal'nym
Privet vsem collegam, vsem kogo znaju lichno i pomnju a takzhe vsem ostal'nym
Vash Ilya
--------------
A short history of AEROFLOT first
computerized schedule
The computation Center in the Civil Aviation Institute
was founded probably in 1964. It had a group which started working
on computer applications in AEROFLOT. The work of this group gave no
visible results, as we found later, and was concentrated around
hopeless trials to apply integer programming to make the schedule.
Institute administration decided to organize a new Department in the
Computation Center under the guidance of Khaim Borisovich. I
started to work there since September 1965. Kh. B. nominated a small
group of people which included Vald Linis, Valery Venevcev, Misha
Maksim and myself, and we were given the task of making the central
AEROFLOT schedule using computers. We had no idea what really the
schedule is and how to do it, neither manually, nor by aid of a
computer.
After some time spent in heated discussions which
resulted in nothing, a wise decision was made by Kh. B. who said:"
Before we do the schedule using computer, we must learn how it is
done now manually, without computers". As a result, Valery and
MIsha were sent to Moscow, to the Ministry to take part in the
actual scheduling process. In sixties, there were two sessions each
year, approximately one month each, for winter and summer
navigations, respectively. The schedule was made by a very smart
man named Sharkevich and a small group of two-three his technical
aides. Sharkevich kept in his phenomenal memory literally hundreds
of flights together with their arrival/departure times. Valery and
Misha were present in two sessions. Upon their return, we discussed
what they saw and understood. The input information for the schedule
were so-called local projects submitted by separate territorial
branches of AEROFLOT (local companies). Already on the stage of
preliminary analysis of this input, it was necessary to solve a
series of fleet optimization problems whose goal was to minimize the
number of aircraft involved in the schedule. As the result of this
stage, the basic "flights" which had to be nominated their
arrival/departure times, were not separate
flights but chains of flights
termed in AEROFLOT "turnover chains" (TC) ("Grafiki
oborota"). The next and most crucial part of the scheduling
procedure was choosing the exact arrival/departure instants for each
flight. All these instants were rounded up to 5 minutes, and each 5-
minute interval was permanently attached to a certain arrival or
departure. In doing this attachment, it was necessary first of all
to guarantee some important safety conditions demanding special time
intervals between arriving / departing aircraft using the same
exit/landing corridor. In formal terms, the manual procedure was of
greedy type, without backtracking, which means that the TC's were
positioned using some heuristic priority
rules. The highest priority were given to
the international flights, next – to the flights delivering
newspapers, then - multi-leg flights to Siberia from Moscow, and so
on. Upon understanding the existing priorities, we were able to
design a computerized assignment of ranking the TC's according to
their priority.
As in many real-life problems, there was no unique
optimum criterion for the whole schedule but rather a hierarchy of
criteria for each stage of the scheduling process. So, after
determining the scheduling sequence according to the priority rank,
each TC was positioned into the schedule according to the local
criterion who was aimed at minimizing the total penalty of the
deviations from the "ideal" arrival/departure times given
in the input. Kh. B. took active part in formalizing the local and
global criteria which were eventually finalized based on computer
experimentation.
Our first serious computer trial was made in 1967 on
URAL-1. This was a huge electronic brontosaurus which occupied the
whole space of an old Pravoslav church located in the middle of a
site belonging in those times to Civil Aviation Institute. URAL-1
had a very small fast memory and several magnetic drums of relatively
large capacity. However, frequent information exchange between the
central processor and the drums immediately led to a failure, so that
a serious work couldn't be made on this computer. We tried also
another URAL-1 in Tartu University, with the same unfortunate
results. Nevertheless, we were able to check the global and local
priority rules, and toward the end of 1968 the main principles of
doing computerized schedule were ready for implementation.
As far as I remember, in 1969 we already were in the new
building of the Computer Center, near the main campus of the
Institute, where we continued our work on the new computer MINSK-22
consisting of two original computers with joint fast memory of 8192
30-bit words + 8 magnetic drums each with memory of 16,384 30-bit
words. The whole system was hardly able to work without failure more
than 4-6 hours. We were forced to split the whole input of about 1000
TC's into series of small portions of 50-100 TC's. After processing
a portion, we repeated the process and went to the next portion only
after two successive results were identical. Doing the whole schedule
took about 24 hours of work.
In the end of 1970 we were ready to do the "real"
schedule for AEROFLOT but the Ministry did not hurry to use our
experience. The people in Ministry were not convinced that we will
be able to do the job. I am not excluding that some people there were
not willing to transfer their exclusive role of making important
decisions (accept or decline a proposal about opening new airline
connection, for example) to some distant people who operate with
such strange arguments as "computer-based decision". But
here came a blind chance which made the Ministry urgently ask for
our help: Sharkevich suddenly died from throat cancer, and nobody of
his aides was capable of doing his unique work. So, the winter
schedule of 1971 was made in our computation center. Under the
guidance of Kh. B., the whole procedure of analyzing and optimizing
the local scheduling projects was made in Riga, when the
representatives of all local AEROFLOT companies came to us with their
projects.
There were several occasions when we had to make
important decisions without having enough experience and
knowledge. For example, we had to decide which of the two local
companies has to carry out a certain "profitable " air
connection, for example Ukrainian- or Moscow- located company. Here
again Kh. B. demonstrated his outstanding skills and talents. He
simply made a series of meetings with several very experienced
people from the local companies and told them approximately the
following : teach us how to make a right decision in these and these
circumstances. He got several very good and honest advices , in
particular from one expert from Moscow. After several lessons, we
learned the principles and smoothly went though the painful process
of accepting/correcting the local scheduling projects. Misha Maksim
put all the projects through the procedure of estimating and
minimizing the fleet size. It made an enormous impression as the
people from the local companies were taught the interactive
step-function technique used for the optimization purpose.
Kh.B. also insisted on printing the whole schedule on a
computerized linotype machine which was able to make all set-up work
automatically by receiving appropriate commands from a perforated
tape. Vald Linis made and extraordinary programming work transferring
all the information from computer-made schedule into the form needed
for this linotype machine. The work was made in typography No 3 in
Riga, located on the former Lenina street 137/139. The next
schedule was made on the yearly basis, and the typing process was
transferred to Moscow. As far as I know, the set-up work was manual.
My information ends on April 1, 1972, when I left the
CNIIASU GA, and I know very little about the further developments.
Комментариев нет:
Отправить комментарий