• home
  •  > 
  • Graphics and design
  •  > 
  • A program for scheduling lessons on Sanpin. The problem of complete automation when drawing up a school schedule

A program for scheduling lessons on Sanpin. The problem of complete automation when drawing up a school schedule

annotation

This article introduces the reader to a unique, recently appeared algorithm for creating a school schedule. 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. Forecasts are made for the further development of this software. 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 due to constant progress and universal accessibility computer 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 , equipped with a powerful uninterruptible power supply system and a microclimate support system. Such electronic computers were primarily intended to solve unique scientific and technical problems that had an impact on the country’s defense capability. Today, many people have personal computers on their desks at home. But just think about it. There are 125 - 250 times more such personal computers compared to the above-mentioned giant. Performance is more than 1000 times faster. And this is not a typo. More than a thousand times.

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. 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. But time passed. Technologies for the production and design of computer technology have developed at a rapid pace. As a result, the performance of computers grew at an unprecedented pace, and their costs quickly decreased. Prices for computers were steadily moving from astronomical to earthly (albeit still exorbitant). By 1965, the circle of scientists who had access to computer technology for research had grown quite noticeably. To this time (the beginning of the sixties), as noted above, the first publications on the topic of compiling a school schedule on mainframe computers date back to this time. It is quite natural that the work was at first staged in nature, and later theoretical. It took about fifteen years to come up with everything that could easily be thought of in relation to the task of drawing up a school timetable. This period (from 1965 to 1980) evokes sharp mixed feelings. On the one hand, beautiful and original mathematical models of the problem of compiling a school schedule were proposed (vertex coloring of graphs, edge coloring of graphs), and on the other hand, without any doubt, these models should be classified as a very simplified version of the problem. In other words, the problem was not completely solved or even formulated in detail. Moreover, in 1976, a work by Israeli mathematicians appeared where, in their opinion, the fundamental difficulty of solving the problem of drawing up a school timetable was proven. So, by 1980, despite the fact that the productivity of computers was constantly increasing and their cost was constantly decreasing, as a result of which civilian industrial enterprises had already moved into the category, took a turn from actually drawing up class schedules to recording and monitoring student progress. Let us emphasize once again that the overwhelming majority of school administrations did not even know about the existence of such programs. However, by this time (naturally abroad) among some “egg-headed” students, a fashion arose for construction kits made from radio components. An era has dawned personal computers . Fashion turned out to be very sticky and the circle of “eggheads” was steadily expanding. It is very likely that designers from radio components would have remained the lot of a handful of “not normal” if the largest manufacturer of typewriters at that time, and one of the most common computers at that time, the American corporation IBM, around 1985, had not perspicaciously I would not have realized that these designers, if given the shape of a typewriter, could replace these typewriters. And not just replace, but make a super intelligent typewriter out of a typewriter, competing with “lead technologies” in publishing. Of course, at that time, no one, except perhaps the most visionary, could have imagined that designers made from radio components would ever be able to compete with real computing devices. However, the die was cast and mass production of typewriter killers began. It didn’t take long for the idea of ​​first “two-in-one” production to emerge (a typewriter plus a businessman’s assistant - spreadsheet), then “three in one” (plus an accounting program), then “four in one”, and so on, and so on, and so on. Yesterday's monovenium students magic wand the respectful abbreviation “PC” was introduced, which meant a personal computer, and already in the early 90s of the 20th century no one doubted that on their desk there was not a toy, but a completely real electronic computer. And indeed, at the very end of the last century, an incredible number of manufacturers, once again, but already, as it seemed to them, at a new technical and technological level, took up the development of programs for compiling a school schedule. Against the backdrop of the cessation of noticeable (albeit gradual) growth in the productivity of personal computers and the stabilization of ideas in the field of software, programs developed that could be classified as third-generation programs. The main feature of these programs, it seems to us, is that they could be developed taking into account both errors and original findings of their predecessors. Here we primarily mean the developers of the nineties. With the mathematical results of the sixties, seventies and eighties, the situation is simpler. If you know about them, then you use them; if you don’t know, then you “invent a new wheel.” Another feature is that these programs were developed using a new graphical user interface at that time. There is no doubt that the graphical interface provides the developer with fundamentally greater opportunities compared to the pseudo-graphic (text) one. But at the same time, there is danger in this. If we begin to compare the school schedule programs available on the market (in use), we will discover an absolutely amazing variety of ways to generate (enter) the initial data necessary for the calculation, although from a mathematical point of view all programs do (or according to began to turn into billionaires, and former designers of radio components began to look more and more like real electronic computers. In technical and, should do) exactly the same thing. Thus, the quality of school timetable programs began to be significantly influenced by the consistency and convenience of the user interface.

Today (2013) it is worth noting that compared to the programs of the nineties, third generation (zero) programs have become quite “wiser”. The developers' optimism has noticeably diminished. No one (or almost no one) is promising complete automation of everything that comes to hand.

Many of the projects started at the end of the nineties have now ceased to exist due to their lack of demand. Others continue to develop and improve. Still others have frozen in their development over the past ten years. But as previously noted, it is still too early to talk about a final and irrevocable solution to the problem of drawing up a school schedule. 3 Are such programs necessary?. 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. . 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.” 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 regular editor mode (like the familiar text editor ) or the use of 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. At least 99 classes. At least 216 teachers. At least half part-time. We will divide the class into groups of at least 256 groups. There are any restrictions for teachers and subjects. Each teacher chooses working days and hours that are convenient for him. There are no windows for teachers. Classes in subjects are held only during the hours permitted for these subjects. Strict adherence to parallels. Each subject is assigned difficulty scores. Exact compliance with sanitary standards of the distribution of the total complexity of items over time is guaranteed.” - they say without hesitation. By the way, this simple move is taken by the developers of the most helpless programs in terms of automatic scheduling and, moreover, sloppy in appearance (although there is one that looks very attractive). Microsoft aptly dubbed such programs “food dogs.” It is difficult to say what exactly motivates people who commit direct and simple deception of consumers. This deception always becomes obvious the first time you enter curriculum schools into the program. According to 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.

4 A little about the complexity of the problem being solved

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, we give a quote from a famous Russian 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. contagious. Sometimes it proceeds relatively easily, but in some cases it becomes protracted or even threatening. There are no vaccinations against it; However, people with a fairly healthy body after a short outbreak acquire lifelong immunity. A person can get sick with this disease several times, and it is sometimes accompanied by acute pain, but not a single fatal outcome was not registered. 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 common border must be painted 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 promoted 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 remains automated system on scheduling classes. 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, he acquires a lifelong, lasting immunity to the task of creating a curriculum. 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 it, buy it, buy it. 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...” So how much does a vacuum cleaner that doesn’t suck up dust, a pan with holes, or a TV that never shows anything cost? Before answering this difficult question, let's try to estimate the number of potential buyers and compare it with the number of schools (head teachers) that have already made their purchase. Demographers have found that about 16% of the population of developed countries are schoolchildren. It is this figure that is used when building new schools in new development areas. Next, we will perform arithmetic calculations using the Russian Federation as an example (our homeland, after all). So, the population is approximately 140 million people. Thus, there are approximately 22 million schoolchildren. There are about 50 thousand schools. This means that the average number of students in a school is 440 people. But this is an average amount. It is known that over the past 60 - 70 years, schools for 1000 - 1400 students were considered standard school projects. Hence the conclusion - there are a huge number of schools with a number of students much less than our average figure - 440 people. Obviously these are schools in schools, programs for scheduling school classes are not needed in principle. 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,” engage in very simple deception rural areas or in very small cities. Hence, a stronger conclusion - a huge number 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. Europe - 500 million people.(hilling). Now all that remains is to convert quantity into quality. That is, multiply the number of potential customers by the price of one software license. In other words, estimate the capacity of the world market in American rubles. But to do this you need to know the price of such a license. I wonder if the reader has ever held in his hands a thick book with something like this title: - “Cost of Software.” But we had to. In fact, the formula is very simple. Software, no matter how complex or large it may be, costs exactly as much as the client (user) pays for it. The clearest example of this is the Windows operating system from Microsoft. Probably few people thought that in terms of the amount of work, talent, knowledge, etc., landing a man on the moon, in comparison with this operating system, is childish pranks. And yet, one hundred and fifty bucks per barrel, and you are a legal user. The only problem is that the number of potential clients - users of the operating system and the program for creating a school schedule - is not comparable, neither in the first nor in the second approximation. Hence the conclusion: - “Despite the fact that some are asking $15 for leaky pots, a program that could really solve most of the problems of head teachers must be expensive.” All that remains is to answer the question: - “What is expensive?”

Of course, everyone has their own ideas about “Expensive”. But probably, for a head teacher (or a similar position, if we are talking about the global market), his monthly salary is expensive. That is, from 1000 to 5000 US dollars. This is what we are actually observing, or at least previously observed, in reality. At first, these programs cost exactly that much on the world market. 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.

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 for modern computer Is this algorithm 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 begin to describe the idea of ​​​​this algorithm, in fact, to a brief summary of the 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 is that the problem is divided into parts, or more precisely, into a series of sequentially solved problems, and each solved problem at the previous step is 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 [,]. 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. New table prohibitions on conducting lessons are built in exactly the same way as in the previous step. The resulting schedule is combined with the prohibition table., 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. So we get new option this table, which we will use in the sixth step. After completing the 4th step of the algorithm, depending on the school curriculum, usually from 15% to 40% of the entire teaching load provided for by this plan is assigned. On the fifth 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. At this step, all previously obtained schedules are combined, that is, the final schedule is formed. To carry out this step, no algorithms are required, simple arithmetic operations are sufficient. After receiving the final schedule, each teacher can decide for himself when it is convenient for him to conduct elective courses. Time for them was reserved at step 3 of the algorithm. And if this teacher can recruit a group of students, then he will independently put his elective course on the schedule, along with the premises selected by him. 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. for the Windows operating system. But what is a regular win application? Once activated (launched for execution), it waits for events from the user, for example, input of initial data. How can this initial data be obtained and later entered into the program? 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. 7 Algorithm testing according to the calculation of 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.

After completing the annual testing of the school schedule algorithm, the question arose: “What next?” First of all, what is striking is that a console application cannot convince anyone that the problem of creating a school schedule is really being solved... except perhaps the programmer who wrote this application. Even a low-performing fifth-grader can create a black window with lines like: “Number of solved problems = 12547564” appearing there from time to time. Thus, a normal person simply will not believe such a program, so to speak, and he will do the right thing. It’s impossible to do without a full-fledged win-application. applications have stuck on more than twenty buttons, of which only one is active at each stage of the calculation, not counting buttons like - About the program, Start a new task, Close me. 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. But first, it wouldn’t be a bad idea to decide on the goals of creating such an application. At least two such targets are in sight. This is the creation of full-fledged software with all the ensuing consequences, and the creation of an application demonstrating the operation of the algorithm, which is better or worse able to convince a person that he is not being deceived. And it’s clear to everyone that in terms of labor intensity, these two projects are simply not comparable. It is quite natural that the decision was made to take the easy path. practical situations that arise when drawing up the school schedule adopted in this program. 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 various publications.

“So what next?” And then the development of full-fledged software in accordance with all the laws and rules of software engineering, which now, in complexity, does not exceed conventional software for ERP systems.

Just don’t ask: - “How long will this take and what is the labor intensity of developing such software?...”. And especially don’t ask: - “How much will such a development cost?...”. 9 Problems with the business model schools and electronic diaries, let me work in peace...” What can be done to change the reputation of such software and the attitude of head teachers towards it from hostile to at least neutral? We won’t talk about a positive image yet. 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? .. still smart for not paying money for it..., my mother told me, “Don’t take a pig in a poke.” About ten years ago, it was still possible to say that computers in the offices of head teachers were for furniture, as an indispensable accessory of scholarship and progressiveness. That in the best case, a computer is used instead of a typewriter (although, as noted earlier, it was precisely this circumstance that contributed to such a rapid flourishing of the personal computer industry). Currently the situation has changed. Many have already tried... We have just discussed the results of such tests. All that remains is to start all over again. Namely. From the business model of distributing such programs. Even without looking very closely, you can see that this business model has remained virtually unchanged over the past 15 years. Find the program website, download the demo version, issue an invoice for payment... Everything seems to be clear with the invoice for payment. It’s also impossible to do without the program’s website. But what about demo versions? But with demo versions everything is different. 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. And the head teacher’s favorite word is: “Busy.” “Oh, busy. I’m so busy that I don’t even have time to breathe.” 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...”.

In short, everything is bad... And so bad, and so inconvenient... Where to look for a way out? Maybe rent?

10 Business model for SaaS software use 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 offering 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 taking risks regarding

a large sum

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 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!

Bibliography

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 Technology in education. Collection of scientific papers. - M.: 1C-Publishing, 2013, Part 2, p. 51 - 55. Gary M., Johnson D. Computing machines and difficult problems to solve. - M.: Mir, 1982. - 416 p.

Distel R. Graph theory: Trans. from English - Novosibirsk: Publishing House of the Institute of Mathematics, 2002. - 336 p.

Therefore, the entire floor where such a computer was located was covered with a fine metal mesh in order to exclude the possibility of “electronic spying” on the part of the sworn enemies of the Soviet regime.

The very task of drawing up an educational schedule (without the help of computer technology) is apparently at least three hundred years old.
Cases have been recorded when head teachers - in general, cultured and well-mannered people, having heard the phrase: - “A program for drawing up a school schedule,” immediately switched to swear words.
Here we will not dwell on the theory of NP-hard problems, since a discussion of this issue would take the reader far away from the topic that interests us, and would also be clearly premature and superficial. The interested reader can be recommended to turn to perhaps the most cited publication on this topic in our country. To fully understand this article, NP-hard problems can be understood as practically unsolvable problems, although this is not an entirely accurate “translation”.
This refers to Russian-language publications, of which there are not so many in comparison with English-language ones. Most likely, their number does not exceed the total contribution of the Russian Federation in the field of high technology, which is estimated at 0.4 - 0.6% (from zero point four percent to zero point six percent) of the global total. True, there are an order of magnitude fewer physical and mathematical sciences.

Vyacheslav Sergeevich Tanaev (1940 - 2002) - Belarusian mathematician, director of the Cybernetics Research Institute of the National Academy of Sciences of the Republic of Belarus, Doctor of Physical and Mathematical Sciences (1978), professor (1980), full member of the National Academy of Sciences of Belarus (2000). Area of ​​scientific interests: operations research, scheduling theory, optimization methods.
Mikhalevich Vladimir Sergeevich (1930 - 1994) - Ukrainian mathematician and cyberneticist, academician of the Academy of Sciences of Ukraine, academician of the Russian Academy of Sciences (1991; academician of the USSR Academy of Sciences since 1984). Works on the theory of optimal statistical solutions, system analysis, theoretical and economic cybernetics. USSR State Prize (1981).

There are eight main modifications of the program for various educational institutions:
. AVTOR School - for 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 education);
. 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 distance learning was put into operation.
. 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 full schedule 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;

    divide classes (study groups) when conducting foreign language classes, physical culture, 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 (archive volume full base High school schedule - 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 - program with unique opportunities. Main advantages compared to similar CIS programs:
. speed, compactness system files and the opportunity to work in a 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 prompts various options 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.).

On September 1, 2011, new SanPiN requirements came into force. A feature of the new requirements is the introduction of a detailed difficulty scale for each subject. Now the difficulty of each subject is assessed in points for grades 1-4, separately for grades 5, 6, 7, 8 and 9, and for grades 10-11. When scheduling, students' heaviest workload, calculated in points, should occur on Tuesday and/or Wednesday.

Programs for scheduling "Rector 3" and "Rector-School" provide support for drawing up lesson schedules taking into account the new requirements of SanPiN. Below we will look at the sequence of scheduling when switching to new SanPiN requirements in the Rector 3 program. All actions in the Rector-School program look similar.

Our plan is this:

  1. Setting up fines for violating SanPiN requirements.
  2. Entering a difficulty scale for each subject.
  3. Drawing up a schedule taking into account SanPin requirements.

The presentation of the material is focused on experienced users. For beginners, we recommend that you first read the program manual.

Setting up fines for violating SanPiN requirements

The values ​​of fines for violating SanPiN requirements are set in the Parameters dialog on the SanPiN tab. To open the dialog, launch the program and in the Settings menu, select the Options command, as shown in the screenshot.

As a result, the Options dialog will open:

Go to the SanPiN tab:

As can be seen from the screenshot, in in this case the values ​​of fines for violating the requirements of SanPiN are equal to 10. In order to give greater weight to the requirements of SanPiN, we will increase all fines to 50:

To save the new values, click OK.

Is it possible to set values ​​other than 10 and 50? Yes, you can. Fines are specified in relative units and must be non-negative numbers. The most important thing is that the fines must be balanced with each other, that is, the fines on the SanPiN tab must be balanced with the fines on the Classes and Teachers tabs.

Why are fines set separately for grades 1-9 and 10-11, since the SanPiN requirements for maximum load are the same for all classes? The requirements of SanPiN cannot be violated, but if we assume that small deviations are possible, then they are more likely for high schools and the program allows you to do this.

Entering a difficulty scale for each subject

IN new version program, in the file with demonstration data, the difficulty scale for each subject has already been entered in accordance with the new requirements of SanPiN. However, if you have been using the schedule program for more than a year, then you probably need to set the difficulty of the subjects in points again, since previously the difficulty of the subject was either constant or depended only on the level of study.

To do this, go to the Lists section on the Items page. Your list of items might look something like this:

Double-click on the line with the name of the item to open the Item Properties dialog.

Make sure that in the List of subjects according to SanPiN window, the program correctly determined the name of the subject (in the screenshot, the name of the subject “Algebra” coincides with the name of the subject according to SanPiN - “Algebra”). In some cases, the program will not be able to independently determine the name of the item according to SanPiN. First of all, this concerns languages. While the program uses the usual “Russian language,” “English language,” “German language.” etc., in SanPiN there is only " National language" and "foreign language". If the program could not correctly determine the name of the item according to SanPiN, do it manually.

Now click on the Install button. A “green wave” will run along the difficulty scale on the left side of the dialogue and the recommended values ​​will be set.

If necessary, points can be adjusted manually.

Drawing up a schedule taking into account SanPin requirements

When automatically creating a schedule (Find button on the toolbar, see Help and Program Guide for more details), the program takes into account the requirements of SanPiN. The program window with your data may look something like this:

On the screenshot:

  1. The difficulty of the subject in points for the current class is 5a.
  2. Total workload of the current class on Tuesday (sum of points in all subjects on Tuesday).
  3. Red color shows the day of the week on which the total load exceeds the load on Tuesday and/or Wednesday.
  4. The day of the week on which the total load is equal to the load on Tuesday and/or Wednesday is shown in brown.
  5. The labels of classes whose schedule has been drawn up, but in violation of the requirements of SanPiN, are shown in pale green.

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

Android

Timetable

Beautiful and intuitive clear application to manage 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.

Schedule - 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 few people use the service yet. But there is a widget and a QR code scanner.

iOS

iSchool

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 your 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 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 quick check schedules.

Foxford timetable

The class-by-class schedule of classes in the Foxford Home School and external studies is 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 of the 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! :)