Online school timetable program. The problem of complete automation in creating a school schedule

annotation

This article introduces the reader to a unique, recently appeared, algorithm for compiling school timetable. The results of testing the only program in the world that can not create, but create such a schedule in a fully automatic mode are reported. Based on the results of tens of millions of tests (built school timetables), the myth about the impossibility of drawing up a school timetable without human participation is debunked. Predictions are made further development this software tool. The SaaS business model for its use is discussed.

To understand the main content of the article, no special mathematical preparation is required, so the article is addressed to a wide range of interested readers.

1. Introduction Over the past decade in Russian Federation At least a dozen dissertations were defended on topics related to the task of drawing up educational timetables. Over the previous decade, the number of defended dissertations was no less. Although dissertations are mainly defended for the title of Candidate of Technical Sciences and the problems of creating a class schedule for higher education are considered educational institution , nevertheless, this fact indicates that more and more researchers are paying attention to the problems of creating a school schedule. Perhaps this stream of work is associated with the constant progress and universal availability of computing technology. Indeed, truly amazing processes are taking place before our eyes. Just twenty-five years ago, only a large, usually defense, enterprise could afford to purchase such an electronic computer as the EC1066. Such a computer was located in a room with an area of ​​up to several hundred square meters

2 Generations of scheduling software

The first publications on the topic of using computer technology to automate the preparation of class schedules appeared in the early 60s of the previous century, so the task of creating an educational schedule using computer technology has a fairly long history. Over almost 50 years of intensive research, enormous intellectual work has been carried out by thousands of specialists around the world. However, the task of creating educational timetables, both then and now, is still a tough nut to crack. It is not at all surprising that programs for creating a school schedule appeared and improved as computer technology developed. Therefore, let us turn (naturally in a telegraphic style) to very conditional periods of this development. Without going too much into historical research and without risking making a big mistake, the appearance of a computer (electronic computer) is possible by 1945. This emergence (again without risking much error) can be attributed to the need for military computing. One of the first tasks that were solved on the first computers was the task of compiling ballistic tables for artillery and aviation. The task of studying atomic and thermonuclear explosions played an important role in the needs of the military. In force above stated reasons » the first computers to a wide range of narrow specialists - mathematicians involved in numerical methods. The result was not long in coming. Since 1955, there has been an explosive growth in such a branch of scientific knowledge as applied mathematics. Hundreds and thousands of practically important problems have become the subject of research by mathematicians using electronic computing technology, which has led to the development of completely new numerical methods for solving these problems. For the reason that the cost of computers was completely incomparable with the economic effect that they could bring for a civilian industrial enterprise, the only users of this technology were the military and a very narrow circle of scientists. In other words, those people who did not know the words - expensive, costs or phrases - economic effect. Perhaps the first generation programs for scheduling classes could be attributed to this period. Opposite trends - the explosive growth in the productivity of former toys, on the one hand, and the rapid drop in their prices, on the other hand, have done their job. In some advanced schools, by today's standards, the leaders' desks now had, by today's standards, huge monitors that screamed like a living reproach: “Fill me with the necessary software.” It’s no wonder that I remembered the seemingly completely forgotten idea of ​​creating a schedule. , the very fact of the existence of a computer and the principles of its operation at first remained classified.. Thousands of lovers of easy money rushed to write programs for schools, guaranteeing complete automation of everything they could get their hands on. This period, perhaps, can be attributed to second-generation programs that automate the process of drawing up school schedules. In the 1990s, the personal computer industry experienced incredible growth. The productivity of personal computers doubled almost every year and every year brought innovative software products. Those working in this field “the soles of their shoes were torn.” But the programs for drawing up school timetables somehow did not want to work correctly... Now, of course, it is difficult to say whether or not the manufacturers of programs for drawing up school timetables knew about the legacy that their predecessors left them in the 1965 - 1980s of the last century and about the warning of Israeli mathematicians in 1976 that this problem was difficult to solve, but the fact remains that the administration of educational institutions was slowly writing off the good old typewriters, replacing them with personal computers. The schedule was still, with few exceptions, compiled manually. century, along with the final dominance of operating systems with graphical user interfaces, comes the end of second-generation school scheduling programs that used the pseudo-graphical interface of the outgoing MS-DOS operating system. The personal computer industry has successfully stopped its rapid development and moved to the notorious “stability”. Personal computing technology surpassed the performance level of large computers in the mid-80s of the last century, everything was ready for the development of third-generation programs. No one (or almost no one) is promising complete automation of everything that comes to hand.

TO

Usually, when talking about the benefits (necessity) of using a program for automated scheduling, they indicate such a factor as an order of magnitude reduction in the work costs (time) of the head teacher when drawing up the educational schedule. It is often pointed out that better quality schedules can be obtained using a computer. Although this argument, taking into account what is said below, is not without controversy. In our opinion, we should agree that calculating the schedule using a computer will, in addition to saving time and obtaining a better quality schedule, on the one hand, exclude subjective assessments and personal sympathies of the head teacher in relation to the teacher (part of the teachers), when drawing up the schedule, in including when distributing the teaching load, and on the other hand, it will completely eliminate undeserved accusations against the head teacher from teachers of such subjective assessments and sympathies, since it is obvious that the computer is “a person not interested” (the computer is “to blame” for everything) . Thus, calculating the distribution of teaching load and schedule on a computer can improve the psychological climate in the teaching staff (comply with the principles of fairness and equality), just as the match referee improves the mood of the players of a football team after deciding the right to kick the ball first using a draw. . In 2001, the Chronobus company conducted a survey of almost 1000 Moscow schools on the need to create and implement an automated workplace (a) “Schedule”. The survey results showed that all schools have a sincere desire to use such a program, but no one does it. Moreover, the reason for the unanimous disregard of such automation tools is not the lack of necessary equipment or money, but the quality of the programs offered on the market. The phrase: “If I were offered to increase my salary by one and a half times because I use such a school schedule program, then I would refuse this offer” was not uncommon. In other words, according to the head teachers, school timetable programs are software with a negative cost. and it was not without reason that a persistent negative, and often aggressive, attitude was formed. Misleading advertising about the imposed “school information space” creates an image of the authors of this space as scammers selling rotten goods. According to head teachers of schools with extensive work experience, Experienced masters of their craft recommend that beginners, when creating a lesson schedule, use a dozen or more tips, proven by many years of experience and practice, using, instead of a computer, lesson schedule table layouts made from sheets of cardboard, colored paper, wide transparent tape, glue, pockets and so on. And they are certainly right. Using a computer in the mode of a regular editor (like a familiar text editor) or using programs that lead the process of arranging classes into dead-end situations, when not a single lesson can be theoretically fit into the schedule grid, can bring nothing but unjustified difficulties, inconvenience and anger. In our opinion, this is a very balanced and worthy position, which, despite a little cunning, can only inspire respect. Or, at least, it does not cause an aggressive attitude towards developers on the part of users. practice shows that these programs can only be used as a tool for the initial arrangement of objects with subsequent manual finishing, as well as storing information and printing it out. After the automated distribution of objects (the program, as a rule, arranges from 40 to 70%), it is practically impossible to take into account the hygienic requirements for the lesson schedule, since it is necessary not only to deliver the remaining unarranged objects, but also to significantly change (up to 60%) the automated arrangement of objects according to the principle “just to arrange it.” Russian legislation

, in accordance with Art. 179 of the Civil Code of the Russian Federation, transactions made under the influence of deception can be declared invalid by the court, while the deceiver returns all the money received to the deceived, compensates the deceived for real damage and, in addition, must transfer to the state income the same amount that he received from the sale of the program.

It is worth saying a few words about the complexity of solving the problem of creating a school schedule. To qualified users of a personal computer who believe in its omnipotence, it seems that the task of creating a school schedule is almost more difficult than the task of creating, for example, a high-quality video editor or sound editor. However, as mentioned earlier, the number of researchers who have studied this problem in one way or another is difficult to count. Among them are dozens of doctors of technical and physical and mathematical sciences, hundreds of candidates of science, not only technical, but also physical and mathematical, not to mention thousands of ordinary lovers of mathematical puzzles, which certainly includes a large army of students in technical and physical and mathematical fields of study. Among the researchers of the problem of compiling a school schedule, two academicians can be mentioned - V.S. Tanaev and V.S. Mikhalevich, one could also name foreign scientists of world renown. In addition to scientists, outstanding businessmen did not ignore the task of drawing up school schedules. And yet, despite, without exaggeration, the titanic efforts of researchers, there is no need to talk about a complete and comprehensive (or at least satisfactory) solution to the problem of drawing up an educational schedule.. To confirm what has been said, here is a quote from the famous domestic mathematician ... Since the task of creating schedules is well known to everyone from school life, in each course there are one or more students overwhelmed by the idea of ​​​​algorithmizing the creation of a class schedule. Therefore, I have to warn you that this is a very difficult task. ... There is a special science - scheduling theory, which studies and systematizes problems of this kind, as well as various approximate methods for solving them (there is almost no hope for exact methods). A special place among them is occupied by heuristic methods, in which attempts are made to describe the logic and technique of the dispatcher’s actions. ... One interesting observation. But first, let's give one more quote. After a short outbreak, they acquire lifelong immunity. A person can get this disease several times, and it is sometimes accompanied by severe pain, but no deaths have been recorded. There is at least one known case of the disease being passed on from father to son, so it may be hereditary. Here, an outstanding American mathematician sneers at the ancient problem of coloring a political map in four colors, where countries with a common border should be colored in different colors. It seems that everything he said can be attributed to the task of drawing up a school timetable. So, the author of these lines decided, to the best of his ability, to track the future careers of people who defended their dissertations on the relevant topic. It would seem that “God himself” ordered the newly established scientist to turn his scientific achievements into money. That is, somehow bring your brainchild to the market, since almost always after defending a dissertation, some program or part of an automated system for scheduling classes remains. So - no. All cases of dissertation defense on this topic known to the author end in one way - after the defense, the dissertation candidate gives up this task and, as a rule, begins (or continues) a career as a teacher at a university. In other words, it acquires lifelong, lasting immunity to the task of drawing up a school schedule. To conclude our general discussion about the complexity of solving the problem of drawing up a school schedule, let us refer to two more opinions. But first, let’s pay attention to who expresses this opinion. also causes people with technical education to try to automate the activities of dispatchers at their favorite university. But these opinions, to put it mildly, are not of great interest. Professional mathematicians, specialists in the theory of schedules, speak out about the problem of drawing up an educational schedule extremely rarely. Therefore (or even more so) their opinion on this matter seems very interesting. So. Sotskov Yuri Nazarovich, Doctor of Physics and Mathematics. Sciences, professor, chief researcher at the Joint Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, one of the most prominent specialists in the field of scheduling theory, author of a number of monographs on scheduling theory. In his article, in particular, he writes: ... From a mathematical point of view, the problem of constructing an optimal training schedule is quite complex, since it belongs to the class of so-called NP-hard problems. ... This article shows how coloring the vertices of a graph can be used to construct a training schedule. ...... The graph vertex coloring problem is NP-hard, and hence its generalization described in Sect. 2 is also an NP-hard problem. ... Further. Lazarev Alexander Alekseevich, Doctor of Physics and Mathematics. Sciences, professor, chief researcher at the Institute of Management Problems named after. V.A. Trapeznikova RAS, Moscow, one of the most prominent specialists in the field of scheduling theory, author of a number of monographs on scheduling theory. In his article, in particular, he writes:... The educational scheduling problem is a well-known combinatorial optimization problem called “timetabling”. Even finding a feasible schedule is a strong NP-hard problem. Therefore, when solving it, it is necessary to use mathematical methods for solving combinatorial optimization problems. ...

In short: - “Drain the water, dry the oars, turn out the lights...”

The market for scheduling software, which developed along with the market for any software for personal computers, seems simply unique, or at least surprising, or at worst very strange. So what makes it unique or strange? Have you ever seen an advertisement like this: - “Buy our vacuum cleaner that cannot suck up dust.” Or this: “All the pots that we can offer you are full of holes.” Or this: “Our TV is unique - it never shows anything.” And here is the advertisement: “Buy our program for creating a school schedule, which cannot create it, but can create it,” we had to see as much as we wanted. “Well, buy, buy, buy. Our program can also create a schedule. She will arrange almost all the classes for you, but let’s do the rest ourselves. Getting out of a dead end is so interesting. Well, at least for 15 dollars. It’s not a lot of money, we worked so hard...” or in very small cities. Hence, a stronger conclusion is that a huge number of schools do not need programs for scheduling classes in principle. It is, of course, very difficult to estimate the number of schools that do not need such programs in principle. However, if we look carefully at the ceiling we will see a figure there - 70%. From which it follows that 30% of schools have a student population of 500 or more, and for such schools a program that cannot create a school schedule, but can create one, would not hurt. We get the final figure - 15 thousand schools. This is, perhaps, the potential market capacity for the Russian Federation. But what do we have in reality today? The question is not simple. There are no reliable statistics. First of all, one program comes to mind, which was “free of charge” for all schools in the Russian Federation. The development of this program began in 1998, and the end ( latest version, especially for its time, the program is certainly not bad. Compared to other similar programs, it has a very logical and thoughtful user interface. In our subjective opinion, the best user interface. However, although there is a Create a schedule button, the program is absolutely helpless in terms of automatic (without human intervention) scheduling. It is not able to solve even those simple subtasks that other programs can easily handle. Judging by the reviews on the Internet, almost no one uses this program. So, we will consider it a “radiation background” that does not affect the overall market situation. Let's move on. Let's pose this question. Are there programs on the market that can provide the head teacher with at least some assistance in creating a schedule? For example, many head teachers manually draw up a schedule in two stages. At the first stage, according to their expression: - “They deal with foreigners.” In other words, they create a schedule for teachers and classes when studying a foreign language. The second stage is everything else. At least two programs on the market cope enviably well with this first stage. Here you can plan the timing of elective courses. In this case, from 10 to 40 percent of classes are arranged. So, of course, there are some benefits from using a computer equipped with these programs. Moreover, one of these programs is very aggressively and persistently trying to complete the schedule. In some cases, albeit rare ones, she succeeds. The other, when completing the schedule, is absolutely helpless. calculating the number of potential customers is this way. We take the population of the country, discard four zeros, and get the number of potential clients. That's what we'll do. The drop in prices, it seems to us, occurred precisely because it suddenly turned out that a pan with holes was bought for $5,000. So how many people today use software for scheduling classes in the Russian Federation? Some manufacturers of such software publish information about their clients on their websites. True, this information should be treated very carefully. As noted above, some manufacturers, in “fits of marketing,” resort to very simple deception of potential customers. And yet, separating the wheat from the chaff, we get a figure of about 1,500 schools. Which is about 10% of the potential market capacity. Therefore, 90% of potential clients have not yet been converted. Now let's turn our attention to the world market. As follows from previous calculations, very

in a convenient way

In the spring of 2012, an archaeologist turned to some programmers he knew with a strange request. According to him, while deciphering ancient Egyptian manuscripts, he came across a description of an algorithm for compiling a school schedule. The authorship of the algorithm was attributed to an Egyptian priestess named Anush. Actually, his request was to check on a modern computer whether this algorithm is really capable of creating a school schedule. At first his friends laughed at him. But after carefully reading the strange records, we still decided to check them. So, let's start describing the idea of ​​this algorithm, essentially summary translation of an ancient manuscript. Let us first say that the very terminology of this algorithm and the organization of the ancient Egyptian school are of separate historical interest, but since this article is not intended for historians, we will present the algorithm in modern terminology familiar to people living today. The main difference between the ancient Egyptian algorithm (hereinafter we will omit the word ancient Egyptian) from modern approaches lies in the fact that the problem is divided into parts, or more precisely, into a number of sequentially solved problems, with each solved problem at the previous step being a constraint for the problem to be solved at the next step. In modern terminology, the method of decomposition of the problem being solved is used. It should be noted that each individual problem that is solved sequentially during the algorithm is not NP-hard (unsolvable). This allows, by sequentially solving a series of easily solvable problems, to solve the entire problem of creating a school schedule. a schedule for part-time workers is being built. It turned out that ancient Egyptian educational institutions did not disdain part-time work. The main feature of this task is that part-time workers are allowed to declare in an ultimatum form the days on which they will work. In addition, some part-time workers are allowed to refuse work on the first lesson of all working days when they work. Apparently these part-time workers were women and they could not come to school early. The problem is solved using an algorithm for prescribed coloring of the vertices of an ordinary graph. You can get acquainted with this mathematical model in detail using the already mentioned article or with the help of numerous other journal articles, for example, [,], as well as by getting acquainted with books [,]. Next, for each lesson (class, teacher, time), using an algorithm for solving the assignment problem, a room for conducting this lesson is selected. The algorithm for solving the assignment problem is described in many modern textbooks; in particular, you can get acquainted with it in the book. The end of the second step is the operation of combining a table of prohibitions on conducting lessons, built in accordance with sanitary restrictions and the resulting schedule for part-time workers. Thus, we get a new table of prohibitions on conducting lessons, which will be one of the restrictions for consists of solving the problem of conducting classes of students' choice (in our terminology, elective courses). The peculiarity of this task is that a certain number of classes, at a certain school hour, are combined into streams, and then at that hour they disperse to their elective courses. The construction of the schedule will consist in the fact that each stream will be assigned a time at which elective courses will be held, but teachers will be appointed after the entire schedule has been finalized. That is, at this step, teachers are not assigned to conduct elective courses. When constructing the schedule, the rule is observed - for any stream in one academic day, no more than one academic hour can be assigned to conduct an elective course. In addition, another rule is observed - elective courses cannot be scheduled for more than one stream at any given time. This rule (restriction) seems quite reasonable, since when conducting elective courses, the need for premises for conducting classes increases sharply. It was introduced precisely for the purpose of avoiding a situation where several threads at the same time require a large amount of free space. At this stage, premises for conducting elective courses, as well as teachers, are not selected; they will be selected together with teachers after constructing the entire schedule. The algorithm for solving the problem of conducting elective courses is the algorithm for prescribed coloring of the vertices of an ordinary graph, which we pointed out when describing the previous step., may be required to be excused from classes during the first hour of the working day when they work. The problem of scheduling teachers/classes for studying a foreign language, just like in the second and third steps, is solved using an algorithm for prescribed coloring of the vertices of an ordinary graph. In the same way as in the second step, using an algorithm for assigning each lesson, or rather, each group of students and their teacher, a room is selected for its conduct. The end of the fourth step, as well as the second and third, is the operation of combining the table of prohibitions on conducting lessons with the resulting schedule. Thus, we get a new version of this table, which we will use in the sixth step. a schedule is built for all remaining subjects except those taught in scarce premises. Teachers do not have the opportunity to declare an ultimatum about which days they will work, but for those teachers whose workload is low, one or two days off are guaranteed, and for some teachers there is the opportunity to refuse to work during the first lesson. This problem is solved using a prescribed edge coloring algorithm for a bipartite multigraph. You can get acquainted with the idea of ​​​​this algorithm from a book or from journal articles [, , , ,]. The constructed schedule consists of fours - class, teacher, subject, time. At the same step, all fours, using an algorithm for solving the assignment problem, are matched with the premises where these classes (fours) will be held. After completing this step, the entire schedule is filled, with the exception of classes held in scarce premises. However, the remaining “holes” in the schedule are the schedule for conducting classes in scarce premises. Thus, we can consider that at this sixth step, in a sense, two schedules are simultaneously constructed - for regular teachers/classes and for scarce premises/classes. On the seventh step classes are divided into groups according to subjects that will be held in scarce premises. As a rule, in subjects such as physical education, labor (technology), and computer science, classes are divided into groups. If the set of teachers for whom the schedule was built in the previous step intersects with the set of teachers conducting classes in scarce premises, then a table is formed for the prohibited working hours of teachers, which is the intersection of these sets. Using an algorithm for solving the assignment problem, teachers are selected for each group. on the schedule, along with the room he himself selected. The general rule for all previously described steps, except for the fifth, is the rule - each class cannot have more than one lesson in any subject on one day. Besides,

general rule

for teachers is that each teacher can teach classes in several subjects, including one class. 7 Algorithm testing and those who translated it. It will be possible to obtain statistically reliable data on the quality of the tested algorithm. For example, 80 percent of problems are solved, but 20 are not, or vice versa. You just need to make the number of tasks to be solved large enough. This is exactly what had to be done - a console application, this was the way out of this situation. As can be seen from the previous section, there is nothing difficult to understand in the operation of the algorithm for constructing a school schedule. One after another, individual easily solvable (non-NP-hard) problems are solved, interconnected, until they are all exhausted. Nevertheless, there was no basis to assert with confidence that each of these problems could be solved. In the absence of any theoretical justification for the algorithm, it was possible to test its performance only experimentally, especially since this was precisely the task posed by the archaeological scientist who stumbled upon ancient manuscript a small amount of classes from 22 to 28. The brakes were clearly on... The process began to resemble a lazy duck waddling from foot to foot. But one thing was pleasing - the line: “The number of unsolved problems =” constantly showed zero.

It became clear. To obtain statistically reliable data confirming the possibility of solving any reasonable problem in a fully automatic mode, one computer is not enough. Small arithmetic calculations showed that in order to operate with numbers of six or more digits about the number of solved problems, at least a dozen computers are required. And for a dozen computers (you can estimate the amount of heat generated from these computers and the constant noise emitted from the fans) a separate room is required. But nothing, you can’t stop us... A dozen, not a dozen, but seven four-core computers were soon put into operation.

After completing the annual testing of the school schedule algorithm, the question arose: “What next?” When you click on this button, a window appears with a Data Generation button. You click Data Generation, and the generated data appears in a window on a white background. We close the window. The button that was just pressed goes out (no longer active), the next one to be pressed becomes active. Click. The following window opens. And there is a button Create a schedule. Click on Build schedule, the constructed schedule appears. Anyone can check whether the schedule is built correctly or not. And so on until all steps of the algorithm have been completed. And then you can click on the big Start a new task button. And so on in a circle. Or click the Close me button. Such an analysis or examination could be carried out by specialists who are well acquainted with the topic, for example, head teachers with sufficient work experience who teach mathematics at school. To understand the details of the calculation, of course, their qualifications are not enough (and no one would have such a desire), but due to the general mathematical culture they have acquired, they can discern obvious omissions in the formulation of the problem much better than any professional mathematician who is familiar with the work of the school only by hearsay or As a result, after a year of “violent actions” of the ancient Egyptian algorithm in relation to the venerable quad-core seven, and after tens of millions of solved problems, we can say with confidence: - “Any, without exception, reasonable, correctly specified task for calculating the school schedule, can be solved without human intervention in a fully automatic mode.” At the same time, the total calculation time for 1000 problems is approximately the following: for a group of problems from 9 to 14 classes = 20 minutes, for a group of problems from 15 to 21 classes = 40 minutes, for a group of problems from 22 to 28 classes the calculation time is from 6 to 8 hours, i.e. for this group, on average, about half a minute per task. Thus, more than a year-long experiment to verify (test) the algorithm for compiling a school schedule in a fully automatic mode, without human participation, for which tens of millions of test tasks were solved, was successfully completed. For almost all test tasks (initial data), a schedule was completely constructed that satisfied all restrictions.

8 Logical model of future software

As previously estimated, the global market for school schedule software, in a fully automatic mode, ranges from 100 million to 500 million US dollars. However, this market, as venture investors say, still needs to be “raised.” And here, at least two problems emerge quite clearly. One problem is: - “Expensive”. We have already stopped there. And another, in our opinion more serious, is: - “The reputation of such software.” If we resort to a metaphor, the reputation of such software resembles one that is dirty, heavily manured and smoking, like after the battle on the Kulikovo Field, garbage dump . Moreover, the smoke is so acrid that you want to close your eyes and stop breathing. As mentioned earlier, when talking to potential clients of school scheduling software, the conversation can easily turn to swear words. “We’re fed up... with our automation, the school’s information space and electronic diaries, let us work in peace...” Our demo version is no different from the working version of the program, but you cannot save the entered data, and you cannot print the results obtained. And so, everything works. Is it possible to use such a demo version to evaluate all the advantages and disadvantages of the program? As noted earlier, to enter all the initial data, no matter how squeaky the advertisement is about an hour, maximum one and a half, it actually requires a minimum of 8 - 10 hours of continuous and painstaking (boring as hell) work. A normal person, and even more so a user starting to work with a program for the first time, when he needs to simultaneously learn how to work with the program and carefully, without errors, enter a mountain of initial data, will not be able to do this in one go. It takes at least two, or even three days (times). Now imagine the beginner’s fear that the power will definitely go out or something will reboot. Well... a normal person would not have the desire to use such a demo version. So, either decide to buy a “pig in a poke”, knowing about the “marketing fits” of some developers, or, as most often happens, press the Del key with bitterness for wasted time.. Having spent 15 - 20 hours working with the program and convinced of its uselessness, shouting: “All programs, like men, are like this...”, potential buyers angrily delete this program from their computer. And after an hour or an hour and a half, having calmed down, having caught their breath, they say to themselves: “How smart I am... after all, I’m smart for not paying money for this..., my mother told me, “Don’t take a pig in a poke.” Option two. Our demo version is no different from the working version, there is only one limitation, the maximum number of classes is five. And so, everything works. As a result, such a statement appears on the forum. “I saw your program, if I may say so. And he introduced that, nothing at all - four classes. And she told me: “I can’t make a schedule.” You can stick it in your... Damn speculators.” Here we are faced with a case where the developers found adventures on their “... (head)”. Those who think that creating a schedule for a school with four classes is much easier than, for example, with twenty, are deeply mistaken. It is for this reason that when testing the “Ancient Egyptian” scheduling algorithm, it was decided that when generating test data, for the minimum number of classes, choose the number nine. This is sometimes explained by the impossibility of automatically compiling a table for the distribution of teaching load. Simply put, distribute the load between a tiny number of classes and, accordingly, a tiny number of teachers. Apparently, such tricks can only be performed by a very experienced hand (or eye, if you like) of a person. Option three. OK then. Use our program. But, two weeks. And in two weeks it’s all over. “We’ll turn off the water...” Is it possible to master the program in two weeks and evaluate all its advantages and disadvantages? Let's put our hand on our hearts: “Perhaps it’s possible...”. But on one condition. You need to stop doing everything else. A favorite word

head teacher: - “Busy.” “Oh, busy. I’m so busy that I don’t have time to breathe or….” Will the head teacher drop everything in the world for two weeks and immerse himself in a timetable program for this period? As scientists say: “It’s hard to say...”.

Initially, the entire computer industry used a rental business model - the first computers cost a lot of money and their computing power was rented out to customers. With the advent of the Internet, the old business model was revived, but on a fundamentally different technological basis. SaaS(English) software as a service - software as a service) - a business model for selling and using software in which the supplier develops a web application and independently manages it, providing the customer with access to the software via the Internet.

The main difference between SaaS and old model is that previously customers accessed computers directly, rather than using global networks. Since the SaaS model is focused on providing services via the Internet, its development is directly related to the development of the global network. The first companies to offer software as a service appeared in Western countries in 1997 - 1999, and the acronym SaaS came into widespread use in 2001. It seems that in our “difficult case”, this business model is the most optimal, and maybe even the only acceptable one. It will save potential clients from risking a relatively large amount of money when paying software product

from a group of products with an almost hopelessly damaged reputation. Using a rental business model, the customer can calmly and gradually become convinced that the product being offered is what he really needs, and that his expectations from using the product coincide with what he actually receives. We previously spoke in some detail about the expectations of head teachers from this type of program.

11 Instead of a conclusion

Sometimes, some people ask sarcastically: “Do you have a business plan?...” Yes. And at the same time, very simple. “Consistently solve emerging problems as they arise...” As a last resort, you can use the SaaS model (business plan - upon request). If anyone needs it, it will be possible to plan everything in detail and not a single accountant will find fault!

Baltak S.V., Sotskov Yu.N. Construction of a training schedule based on coloring the vertices of the graph // Informatics, 2006, No. 3, p. 58 - 69. Borodin O.V. Colorings and topological representations of graphs // Discrete analysis and operations research. 1996, Vol. 3, No. 4, p. 3 - 27. Borodin O.V. Generalization of Kotzig’s theorem and prescribed coloring of edges of planar graphs // Mathematical Notes. 1990, Volume 48, Issue 6, p. 22 - 28. Vizing V.G. Coloring of graph vertices under majority restrictions on the colors used // Discrete Analysis and Operations Research. 2009, Vol. 16, No. 4, p. 21 - 30. Vizing V.G. On connected coloring of graphs in prescribed colors // Discrete analysis and operations research. 1999, Series 1, Volume 6, No. 4, p. 36 - 43. Gafarov E.R., Lazarev A.A. Mathematical methods optimization when drawing up the educational schedule // New information technologies in education. Collection of scientific papers. - M.: 1C-Publishing, 2013, Part 2, p. 51 - 55. Gary M., Johnson D. Computers and hard-to-solve problems. - M.: Mir, 1982. - 416 p. Distel R. Graph theory: Trans. from English - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - 336 p."BLITZ", 2003. - 144 p.

Stetsenko O.P. On one type of coloring of graph edges in prescribed colors // Discrete Mathematics. 1997. Volume 9, issue 4, 92 - 93. Urnov V.A. Schedule - the most popular workstation in education // Informatics and Education. 2001, No. 4, p. 47 - 52. Harari F. Graph theory. - M.: Mir, 1973. - 302 p.

Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems // SIAM J: Comput. Vol. 5, No. 4, December 1976, 691-703 Links:, theoretical and economic cybernetics. USSR State Prize (1981).

However, transferring the source data generator code and the code for checking the correctness of the compiled schedule is quite possible, since this code does not represent any commercial value.
In honor of the ancient Egyptian priestess Anush, the program, in the Russian manner, was named Annushka.
And even... maybe... But what! an empty dream.
There's no way this will happen. Fate is envious and evil!

Oh, why am I not tobacco!...
A.S. Pushkin

File translated from T E X by T T H, version 4.03.

On 27 Jul 2013, 00:53.

Download it to your phone so you don’t forget anything and won’t be late for anything.

Android

Timetable

A beautiful and intuitive application for managing school life. You can enter your schedule, homework, exams, and even vacations. The application can synchronize with all your Android devices, and during classes it will go into silent mode.

School diary

In this electronic diary you can keep a schedule, indicating the name and telephone number of the teacher, as well as the location of the lesson. To make sure you don’t forget anything, the application has widgets for your phone’s home screen. It is also possible to take notes on subjects and grade them. But perhaps the most pleasant feature is crossing off completed homework.

LightSchool

Allows you not only to maintain a schedule and record homework, but also to track the time before the start or end of the lesson. A special feature is the presence of theoretical materials. If you suddenly forgot how to find the sine of an angle, you can look it up directly in the application.

Sign up

Not very colorful, but multifunctional application. You can create a schedule in it and export it to the calendar on your device. You can view your class schedule for a week or several at once and display a widget with reminders on your home screen. During a lesson, the application automatically turns on silent mode, and you can set due dates for homework.

Timetable - school planner

The essence of the application: one user publishes his school schedule so that his classmates can then find a ready-made class schedule. Comfortable! It's a pity that not many people use the service yet. But there is a widget and a QR code scanner.

Allows you to create a beautiful multi-colored schedule indicating the rooms where classes will be held. It’s convenient to write down tasks: you can simply take a photo of the board or dictate by voice. And one more super useful function: you can enter grades in subjects and calculate your average score. The application supports Russian language, synchronization with iCloud works.

iStudiez pro

Allows you to create a schedule with repeating lessons. Each subject can be assigned its own color - this will make it easier to navigate the schedule in the future. You can add holidays and weekends to the calendar, and also save useful information about classmates and teachers.

Class Timetable

Rainbow Planner for Students. The standard set of functions includes a schedule with reminders and a list of homework. But there is also an interesting feature: the application works not only on iPhone and iPad, but on Apple Watch. It’s convenient if, in addition to studying, there are also sports sections and you need to keep up with everything.

Grade Hound

Calendar for schoolchildren and students with the ability to mark subjects by color and assign grades to subjects. The highlight: time graphs that show how much time you'll spend on a particular subject. Minus: does not support Russian language.

Class Schedule – Timetable

Another helper for students who lack organization. You can create a study schedule with repeating or alternating weeks, share it with friends, and write down homework assignments. Thanks to the convenient widget, you don't even need to unlock your device to quickly check your schedule.

Foxford timetable

The class-by-class schedule of classes in the Foxford Home School and external studies is located on the website in the “Educational Process” section.

Select your class and click More Details. You will see what day of the week and what time this or that lesson takes place and you will be able to enter the schedule into your electronic planner.

Also at the beginning school year students receive schedules in the form of convenient pdf tables.

All homework is kept in Personal account student. You just need to select a course and lesson number.

The dashboard will remind you of new and already completed tasks. From there you can proceed to completing the task in one click.

Well, if a student forgets about some lesson or homework, he will be immediately reminded of it. More reliable than any application! :)

There are eight main modifications of the program for various educational institutions:
. AVTOR School - for intermediates secondary schools, lyceums and gymnasiums;
. AVTOR College - for colleges, technical schools and vocational schools;
. AVTOR Art College - for schools of art and culture;
. AVTOR High School - for universities ( Full-time training);
. AVTOR High School Semestric - for universities (correspondence courses);
. AVTOR M High School Semestric - for military universities;
. AVTOR Educational Centers - for training centers, Code of Criminal Procedure and IPC;
. AVTOR High Shool Pro - for universities with several remote academic buildings, taking into account the travel time between them (full-time and part-time forms of study, network version).

History of the creation and development of the system.
. The first version of the AUTOR-2 program (under MS DOS) was developed by RSU researcher Igor Gubenko in April 1993. The program was originally intended for scheduling at a multidisciplinary lyceum at RSU with intensive study of a foreign language, computer science and many special subjects (where classes are divided into 2-4 subgroups and can be combined into streams). Already the first version of the program made it possible to build correct schedules.
. Then the program was tested in several more schools in Rostov-on-Don. The experience of many head teachers and the specifics of the schedules of various schools were taken into account. The program was significantly improved and implemented over 2 years in more than ten schools, lyceums and gymnasiums.
. By 1996, the author managed to develop a unique algorithm for automatically constructing and optimizing schedules, which made it possible to significantly increase the power of the program. In the same year, the first version of AUTOR-2 was released for colleges and for a small university.
. In 1997-98 the author develops and successfully implements the first version of the program for a large university with several academic buildings (RGUE "RINH").
. In 2000, the first WIN version of the AVTOR-2000 program was released for all types of educational institutions.
. In 2001, a version of the program was released with an interface in three languages: Russian, Ukrainian and English.
. In 2001, the first university version for correspondence form training.
. In 2002, a network version of the program for universities appeared with several workstations and a common database of audiences.
. In 2003, AVTOR-2003 was successfully integrated into a single package with the PPP "Plany" (YURGUES), which made it possible to automate the entry of the database into the program and build a complete schedule of this university in 2 hours! In YURGUES (Shakhty) there are 7 educational buildings, two of them are located far away. Previously, the same schedule was compiled manually by two methodologists in 2-3 months.
. In 2004, a version of the AVTOR program was developed for military universities.
. In 2005, a version of AVTOR was released for schools of culture and art, as well as for training centers.

Clients.

Currently, the AVTOR program is successfully used by more than three hundred educational institutions in Russia, Ukraine, Belarus, the Baltic states and Kazakhstan. Among them: Don Real Gymnasium (secondary school No. 62), Classical Lyceum at the Russian State University, secondary school No. 104, No. 38, No. 67, No. 81, No. 52, No. 92, No. 27, No. 46, No. 69, No. 83 (Rostov- on-Don), secondary school No. 297, No. 1117 (Moscow), secondary school No. 315, No. 17, Gymnasium of Oriental Languages ​​(Kiev), secondary school No. 44 (Zaporozhye), Tikhoretsky College of Railway Transport, Beloyarsk Pedagogical College, Rostov Mechanical Engineering College, RGUE "RINH", IUBiP, SKAGS, RGASHM, RGSU (Rostov-on-Don), YURGUES (Shakhty), RGAU named after Timiryazev (Moscow), MU Ministry of Internal Affairs of Russia (Moscow), Irkutsk State University, Institute of Foreign Languages, USPU, USU (Ekaterinburg), SGSEU (Saratov), ​​as well as dozens of other schools, lyceums, gymnasiums, colleges and universities.

Specifications.
The running time of the program depends on the size of the educational institution and the power of the computer. A complete calculation and optimization of the schedule for a medium-sized school with complex initial data (40 classes, 80 teachers, more than 10 part-time teachers; two shifts; shortage of classrooms) takes about 2-3 minutes on a Celeron-2000 computer.

AVTOR allows you to:

build a schedule without "ok"He" in classes (study groups);

optimize in schedule"windows" of teachers;

consider the required range of days/hours for classes, for teachers and for classrooms;

take into account the nature of the work and the wishes of both full-time employees and part-time hourly workers;

optimally place classes in classrooms (auditoriums), taking into account the characteristics of classes, subjects, teachers’ priorities and classroom capacity;

enter call schedule;

installtransition time (transition time)ezda) between academic buildings;

optimize the number of transitions from cabinet to cabinT, and from body to body;

easily connect any classes (study groups) into streams when conducting any classes;

separate classes ( study groups) when conducting classes in a foreign language, physical education, labor, computer science (and any other subjects) for any number of subgroups (up to ten!);

introduce combined lessons for subgroups (such as “foreign/computer science”) in any subjects;

introduce (in addition to the main subjects) special courses and electives;

optimize the uniformity and labor intensity of the schedule;

easily and quickly enter and adjust source data;

have any number of schedule options;

automatically convert schedules when the database changes;

easy to save in archives, copy and send viaE- mailcomplete databases and schedule options (the volume of the archive of the complete database of secondary school schedules is 10-30K, large university - 50-70K);

quickly make any necessary adjustments to the schedule;

find replacements for temporarily absent teachers;

automatically control the schedule, eliminating any “overlaps” and contradictions;

display schedules in the form of convenient and visual documents: text,Word, HTML, as well as filesdBaseand booksExcel;

post ready-made schedules on the local network and on Internet pages for public access.

Difference from analogues.
A comparative analysis of the work of the AVTOR program and programs from other developers has been repeatedly carried out by specialists from various educational institutions. The research results are published on well-known Internet sites, as well as in reports at conferences and master classes. It was concluded that AVTOR has the most powerful algorithm for automatically creating and optimizing schedules: working 10-20 times faster than its analogues, the program builds better schedules according to many criteria. For example, the number of “windows” in teachers’ schedules is 2-3 times less than when using other programs.
AVTOR is a program with unique capabilities. Main advantages compared to similar CIS programs:
. speed, compactness of system files and the ability to work in verylargeeducational institutions with complex schedules;
. high level of automation (accommodates 100% of possible classes);
. high performance:cThe system allows you to create a new schedule during one work session, and then quickly adjust, save, and print various schedule options, modifying them if necessary throughout the academic year;
. powerful automated SCHEDULE EDITOR,whichallows you to easily perform ANY actions with the schedule (adding, deleting, rearranging classes, calculating and optimizing the schedule, changing rooms, replacing teachers, etc.). At the same time, the program clearly and conveniently suggests various options for rearrangements (changes) of the schedule and compares their quality;
. availability of detailed statistics and objective assessment of the quality of any schedule option;
. ability to support any national language (at the client’s request).

Adaptation and configuration of the program.
At the request of the customer, AVTOR is modified and customized to suit the conditions of a specific educational institution (taking into account the specifics of the educational process, operating mode, form of documents, etc.).