Programs for scheduling school lessons. The problem of full automation when drawing up a school timetable
There are eight main modifications of the program for various educational institutions:
... AVTOR School - for secondary general education schools, lyceums and gymnasiums;
... AVTOR College - for colleges, technical schools and vocational schools;
... AVTOR Art College - for art and culture schools;
... AVTOR High School - for universities (full-time education);
... AVTOR High School Semestric - for universities (part-time education);
... AVTOR M High School Semestric - for military universities;
... AVTOR Educational Centers - for educational centers, CPC and IPC;
... AVTOR High Shool Pro - for universities with several remote educational buildings, taking into account the travel time between them (full-time and part-time forms of study, network version).
The history of the creation and development of the system.
... The first version of the AUTOR-2 program (for MS DOS) was developed by Igor Gubenko, a researcher at the RSU, in April 1993.The program was originally intended for scheduling in a multidisciplinary lyceum at RSU with enhanced 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 allowed building correct schedules.
... Then the program was tested in several other 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 has been 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 automatic construction and optimization of schedules, which made it possible to significantly increase the power of the program. In the same year, the first version of AUTOR-2 was published 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 (RSEU "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 with an interface in three languages was released: Russian, Ukrainian and English.
... In 2001, the first university version for correspondence courses was put into operation.
... In 2002, a network version of the program for the university appeared with several workplaces and a common database of audiences.
... In 2003, AVTOR-2003 was successfully integrated into a single package with the "Plany" PPP (YURGUES), which made it possible to automate the database entry into the program and build a full schedule of this university in 2 hours! There are 7 educational buildings in YURGUES (Shakhty), two of them are far away. Previously, the same schedule was compiled by two methodologists manually 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 arts, as well as for educational 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: Donskaya Real Gymnasium (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), school No. 297, No. 1117 (Moscow), school No. 315, No. 17, Gymnasium of Oriental languages (Kiev), school No. 44 (Zaporozhye), Tikhoretsk technical school of railway transport, Beloyarsk pedagogical college, Rostov Engineering College, RSEU "RINH", IUBiP, SKAGS, RSASHM, RSSU (Rostov-on-Don), YURGUES (Shakhty), Timiryazev State University of Economics (Moscow), MU of the Ministry of Internal Affairs of Russia (Moscow), Irkutsk State University, Institute of Foreign Languages of the Ural State Pedagogical University, USU (Yekaterinburg), 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 of a medium-sized school with complex initial data (40 classes, 80 teachers, of which more than 10 part-time workers; two shifts; classroom deficit) takes about 2-3 minutes on a Celeron-2000 computer.
AVTOR allows you to:
build a schedule without "okhe"at the classes (study groups);
optimize in the schedule"windows" of teachers;
take into account the required range of days / hours for classes, for teachers and for classrooms;
take into account the nature of work and the wishes of both full-time employees and part-time employees;
optimally place classes in classrooms (audiences), taking into account the characteristics of classes, subjects, priorities of teachers and the capacity of classrooms;
enter a call schedule;
settransition time (reehd) between educational buildings;
optimize the number of transitions from office to cockpitT, and from body to body;
it is easy to connect any classes (study groups) into streams for any class;
to divide classes (study groups) when conducting classes in a foreign language, physical culture, labor, computer science (and any other subjects) into any number of subgroups (up to ten!);
introduce combined lessons for subgroups (such as "foreign / computer science") in any subject;
introduce (in addition to basic subjects) special courses and electives;
optimize the uniformity and complexity of the schedule;
easily and quickly enter and correct the initial data;
have any number of schedule options;
automatically convert schedules when the database changes;
easy to save in archives, copy and send byE- mailcomplete databases and options for timetables (the volume of the archive of the full base of the secondary school timetable 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, excluding any "overlaps" and contradictions;
display schedules in the form of convenient and visual documents: text,Word, Htmlas well as filesdBaseand booksExcel;
set up ready-made schedules in the local network and on Internet pages for general access.
Difference from analogues.
A comparative analysis of the work of the AVTOR program and programs of other developers has been repeatedly carried out by specialists from various educational institutions. The research results are published on well-known sites on the Internet, as well as in reports at conferences and master classes. It is concluded that AVTOR has the most powerful algorithm for automatic compilation and optimization of schedules: working 10-20 times faster than analogs, the program builds better quality schedules according to many criteria. For example, the number of "windows" in the teachers' schedule is 2-3 times less than when using other programs.
AVTOR is a program with unique capabilities. Main advantages over similar CIS programs:
. speed, compactness of system files and the ability to work in a verylargeeducational institutions with complex schedules;
. high level of automation (accommodates 100% of possible activities);
. high performance:cThe system allows you to create a new schedule during one session of work, and then quickly adjust, save, print various versions of schedules, modifying them if necessary throughout the school year;
. powerful automated SCHEDULE EDITOR,which theallows you to easily perform ANY actions with the schedule (adding, deleting, rearranging classes, calculating and optimizing the schedule, changing classrooms, replacing teachers, etc.). At the same time, the program clearly and conveniently prompts various options for rearrangements (changes) of the schedule and compares their quality;
. availability of detailed statistics and an objective assessment of the quality of any schedule option;
. the ability to support any national language (at the request of the client).
Adaptation and customization of the program.
At the request of the customer, AVTOR can be modified and adjusted for the conditions of a particular educational institution (taking into account the specifics of the educational process, working hours, forms of documents, etc.).
Download to your phone so you don't forget anything and never be late.
Android
Timetable
A beautiful and intuitive school life management app. Schedules, homework assignments, exams and even vacations can be entered. The app can sync with all your Android devices, and during classes it will automatically go into silent mode.
School diary
In this electronic diary, you can keep a schedule by indicating the name and phone number of the teacher, as well as the location of the lesson. In order not to forget anything for sure, the application has widgets for the main screen of the phone. It is also possible to take notes on subjects and put down grades on them. But perhaps the most enjoyable feature is crossing out completed homework.
LightSchool
Allows you not only to keep a schedule and record homework, but also track the time before the beginning or end of the lesson. Feature - the availability of theoretical materials. If you suddenly forgot how to find the sine of an angle, you can see it right in the application.
Schedule
Not very colorful, but multifunctional application. Here you can create a schedule and export it to a calendar on your device. You can view the schedule of classes for a week or several at once and display a widget with reminders on the home screen. During the lesson, the application automatically turns on the silent mode, and you can set due dates for homework.
Schedule - school planner
The essence of the application: one user publishes the schedule of his school so that his classmates can then find a ready-made schedule of classes. Comfortable! It is a pity that few people use the service so far. But there is a widget and a QR code scanner.
iOS
iSchool
Allows you to create a beautiful multi-colored schedule indicating the classrooms where classes will be held. It is convenient to record tasks: you can just take a picture of the board or dictate with your voice. And one more super-useful function: you can enter grades in subjects and calculate the average score. The application supports Russian, sync with iCloud works.
iStudiez pro
Allows you to schedule repeating lessons. Each item can be assigned its own color - so in the future it will be easier to navigate in the schedule. Holidays and weekends can be added to the calendar, and useful information about classmates and teachers can be saved.
Class Timetable
A rainbow planner for students. The standard feature set includes a schedule with reminders and a homework checklist. But there is also an interesting feature: the application works not only on the iPhone and iPad, but also on the Apple Watch. It is 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 put marks on subjects. Zest: timelines showing how much time you will spend on a particular item. Minus: does not support Russian.
Class Schedule - Timetable
Another helper for students who lack organization. You can schedule your activities with repeating or alternating weeks, share with friends, and record homework assignments. Thanks to the handy widget, you don't even need to unlock your device to quickly check the schedule.
Foxford Schedule
The class-by-class schedule of lessons at the Foxford Home School and External School is located on the website in the "Educational Process" section.
Select your class and click "Details". You will see what day of the week and what time a particular lesson takes place and you can add the schedule to your electronic planner.
Also, at the beginning of the school year, students receive timetables in the form of convenient pdf tables.
All homework is stored in the student's Personal Account. You just need to choose a course and lesson number.
The dashboard will remind you of new and already completed tasks. From it, you can go to the task in one click.
Well, if a student forgets about any lesson or homework, he will immediately remind him of it. More reliable than any application! :)
annotation
| This article introduces the reader to a unique, recently appeared, school timetable algorithm. The results of testing of the only program in the world are reported, which may not draw up, but draw up such a schedule in a fully automatic mode. 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 for the further development of this software tool. The SaaS business model of its use is discussed. To understand the main content of the article, no special mathematical training is required, thus the article is addressed to a wide range of interested readers. |
|
1. Introduction
Over the past decade, at least a dozen dissertations have been defended in the Russian Federation on topics related to the task of drawing up educational timetables. For the previous decade, before that, the number of defended dissertations is no less. Although theses are mainly defended for the title of candidate of technical sciences and the tasks of scheduling classes for a higher educational institution are considered, nevertheless, this fact indicates that more and more researchers are paying attention to the tasks of scheduling a school timetable. Perhaps this stream of work is associated with constant progress and the general availability of computing. Indeed, truly amazing processes are taking place before our eyes. Even some twenty-five years ago, such an electronic computer as the EC1066 could only be purchased by a large, usually defense, enterprise. 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 affect the country's defense capability. Today, many have personal computers on their desks at home. But just think about it. The RAM of such a personal computer is 125 - 250 times larger than that of the aforementioned giant. The performance is more than 1000 times higher. And this is not a slip of the tongue. More than a thousand times.2 Generations of Curriculum Scheduling Software
The first publications on the use of computer technology to automate the scheduling of classes appeared in the early 60s of the previous century, thus the problem of scheduling an educational schedule using computer technology has a rather long history. For almost 50 years of intensive research, a tremendous intellectual work has been carried out by thousands of specialists around the world. However, the task of building curriculum schedules, both before and now, is still a tough nut to crack. It is not at all surprising that programs for scheduling school timetables appeared and improved as computing technology developed. Therefore, let us turn (naturally in a telegraphic style) to the very conditional periods of this development. Without going deeply into historical research and without risking a big mistake, the appearance of a computer (electronic computer) is possible by 1945. This appearance (again, without risking too much error) can be attributed to the need for computing for military purposes. One of the first tasks that were solved on the first computers was the task of compiling ballistic tables for artillery and aviation. Not the least role in the needs of the military was played by the task of studying atomic and thermonuclear explosions. Due to the above reasons, the very existence of a computer and the principles of its operation at first remained classified. It took about ten years to bring information about the "tactical and technical characteristics" of the first computers to a wide range of narrow specialists - mathematicians engaged 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 entailed 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 civil 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 - an economic effect. But time went on. Computer manufacturing and design technologies developed at a rapid pace. As a result, the performance of computers grew by unprecedented steps, and their cost was rapidly declining. Prices for computers from astronomical ones steadily approached the terrestrial ones (albeit still exorbitant). By 1965, the circle of scientists who had access to computer technology for research had grown quite noticeably. By this time (the beginning of the sixties), as noted above, the first publications on the topic of compiling a school timetable on large computers belong. It is quite natural that the work at the beginning had a staging character, and later a theoretical one. It took about fifteen years to come up with everything that could be easily thought of in relation to the task of scheduling a school timetable. This period (from 1965 to 1980) evokes strong mixed feelings. On the one hand, beautiful and original mathematical models of the problem of drawing up a school timetable were proposed (vertex coloring of graphs, edge coloring of graphs), and on the other hand, without a doubt, these models should be attributed to a very simplified version of the problem. In other words, the problem was not fully solved or even formulated in detail. Moreover, in 1976 the work of Izrail mathematicians appeared where, in their opinion, the fundamental difficulty of solving the problem of drawing up a school timetable was proved. So, by 1980, in spite of the fact that the performance 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 of active users of computer technology, our task still remained unresolved, and computer technology for the main user - schools, remained inaccessible. Perhaps, the first generation programs for scheduling classes could be attributed to this period. Due to the above two reasons (the difficulty of solving the problem and the inaccessibility of computer technology for the end user), interest in the automatic scheduling of classes has noticeably weakened (and maybe even completely faded away). Higher education institutions using this software have moved from scheduling classes to recording and monitoring student progress. We emphasize once again that the overwhelming majority of school administrators did not even know about the existence of such programs. However, by this time (naturally abroad) among some "egg-headed" students there is a fashion for designers from radio components. The era of personal computers has dawned. The fashion turned out to be quite clingy 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" ones if the largest manufacturer of typewriters at that time, and for one of the most common computers at that time, the American corporation IBM, in about 1985 I would not have realized that these designers, if they were given the shape of a typewriter, could replace these typewriters. And not just replace, but make a typewriter into a super-intelligent typewriter, competing with "lead technologies" in publishing. Of course, at that time no one, except perhaps the most perspicacious ones, could have imagined that designers from radio components would ever be able to compete with real computing devices. However, the die was cast and the mass production of the typewriter killers began. The production ideas were not long in coming and the production ideas, first "two in one" (a typewriter plus an assistant to a businessman - a spreadsheet), then "three in one" (plus an accounting program), then "four in one", and so on, and so on, and so on. Yesterday’s magic wand students began to turn into billionaires, and former designers from radio components began to look more and more like real electronic computers. The respectful abbreviation "Pi-C" (PC) entered the technical and business language, which meant a personal computer and already in the early 90s of the XX century, no one doubted that they had not a toy, but a completely real electronic computer. The opposite tendencies - 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, big monitors appeared on the leaders' desks, which screamed like a living reproach: "Fill me with the necessary software." It is not surprising that I recalled the seemingly completely forgotten idea of scheduling training sessions. Thousands of easy money lovers rushed to write programs for schools, guaranteeing complete automation of everything that only comes to hand. This period, perhaps, can be attributed to second generation programs that automate the process of drawing up school schedules. In the nineties of the last century, the personal computer industry experienced incredible growth. The productivity of personal computers has doubled almost every year and every year brings innovative software products. Those working in this field "had their soles torn on their boots." And 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 1965 - 1980s of the last century and about the warning of the Israil mathematicians in 1976 that this problem was difficult to solve, but the fact remains that the administration of educational institutions was slowly writing off good old typewriters replacing them with personal computers. The schedule was still, with minor exceptions, compiled manually. By the beginning of the 21st century, along with the definitive dominance of operating systems with a graphical user interface, the second generation of school timetable programs that used the pseudo-graphic interface of the bygone MS-DOS operating system came to an end. The personal computer industry has safely stopped its rapid development and moved to the notorious "stability". Personal computing technology crossed the line of performance of large computers in the mid-80s of the last century, everything was ready for the development of third-generation programs. And indeed, at the very end of the last century, not an estimated number of manufacturers, once again, as it seemed to them, at a new technical and technological level, took up the development of programs for drawing up school timetables. Against the background of the cessation of a noticeable (albeit smooth) increase in the productivity of personal computers, the stabilization of ideas in the field of software, programs developed that could be attributed to third-generation programs. The main feature of these programs, as it seems to us, is that they could be developed taking into account both errors and the original findings of their predecessors. Here, first of all, I mean the developers of the nineties. Mathematical results from the sixties, seventies and eighties are easier. If you know about them, you use them, if you don’t know, then you “invent a bicycle for a new one”. Another feature is that these programs were developed using a new at that time - a graphical user interface. There is no doubt that the graphical interface provides the developer with fundamentally greater possibilities in comparison with the pseudographic (textual) one. But in this, at the same time, lies the danger. If we start comparing the school timetable programs available on the market (in use), we will find an absolutely amazing variety of ways to form (enter) the initial data necessary for the calculation, although from a mathematical point of view, all programs do (or at least should do) exactly the same thing. Thus, the consistency and convenience of the user interface began to have a significant impact on the quality of school timetable programs. Today (2013) it is worth noting that in comparison with the programs of the nineties, the programs of the third generation (zero) have become very "wiser". The developers' optimism has noticeably diminished. No one (or almost no one) undertakes to promise full automation of everything that came to hand. Many of the projects started in the late 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 noted earlier, it is too early to talk about the final and irrevocable solution of the problem of drawing up a school timetable.3 Do you need such programs?
Usually, speaking about the benefit (necessity) of using a program for automated scheduling, they indicate such a factor as - an order of magnitude reduction in the labor input (time) of the head teacher in drawing up the curriculum. It is often indicated that a better quality schedule can be obtained with a computer. Although this argument, given what has been said below, is not without controversy. In our opinion, it should be agreed that the calculation of the schedule with the help of a computer will allow, in addition to saving time and obtaining a better quality of the schedule, on the one hand, to 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 in the distribution of the teaching load, and on the other hand, it will completely eliminate the undeserved accusations against the head teacher on the part of teachers, in such subjective assessments and sympathies, since it is obvious that the computer is "not interested" (the computer is "to blame" for everything) ... Thus, the calculation of the distribution of the teaching load and the schedule on the computer can improve the psychological climate in the teaching staff (observe the principles of fairness and equality), just as the referee improves the mood of the football team players after playing the right of the first kick on the ball using the draw ... In 2001, the company "Chronobus" conducted a survey of almost 1000 Moscow schools on the need to create and implement AWP (a) "Schedule". The results of the survey showed that all schools have a sincere desire to use such a program, but no one does it. Moreover, the reason for the amicable disregard of such automation means is not the lack of the necessary equipment or money, but the quality of the programs offered on the market. The phrase: - "If I was offered to increase my salary by one and a half times, for the fact that I use such a program for drawing up a school timetable, then I would refuse this offer" was not uncommon. In other words, according to the head teacher, school timetable programs are negative cost software. Today, after twelve years have passed since the above-mentioned questioning, potential users of curriculum programs - head teachers of schools, to such programs, to an even greater extent and not without thoroughly formed a persistent negative, and often aggressive attitude. Misleading advertising about the imposed "school information space" forms the idea of the authors of this space as fraudsters selling rotten goods. According to the head teachers of schools with extensive experience, practice shows that these programs can only be used as a tool for the initial arrangement of objects with its subsequent manual fine-tuning, as well as saving information and printing it. 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 unplaced objects, but also significantly change (up to 60%) the automated arrangement of objects on the principle "just to arrange". Experienced masters of their craft recommend that beginners, when scheduling training sessions, use a dozen or so tips proven by many years of experience and practice, using, instead of a computer, layouts of the lesson schedule table from sheets of cardboard, colored paper, wide transparent tape, glue, pockets etc. And they are absolutely right. Using a computer in the mode of a regular editor (like everyone is familiar with a text editor) or using programs that start the process of arranging classes in dead-end situations, when not a single lesson is theoretically possible to fit into the schedule grid, can bring nothing but unjustified difficulties, inconveniences and anger. The expectation of users of such programs (head teachers) is beyond doubt. In their opinion, the programs for drawing up a school timetable, after entering all the initial data, should, in a fully automatic mode, draw up a timetable that is superior in quality to the timetable drawn up manually. The inadequacy of user expectations and the result obtained from such programs generates an aggressive attitude of users towards these programs and, together with them, towards the automators "pushing the information space of the school". It should be noted that the developers of programs for scheduling school timetable in the course of "natural selection" were divided into three groups. The first group publicly defends the point of view that the problem of automatically calculating the school timetable cannot be solved in principle. And that's why they “don't be stupid” don't even try to do it. And those who try, in their opinion, are complete ignoramuses. “We do not have a school timetable calculation program, but a school timetable editor. We do not build a schedule for a person, but help a person to build a schedule on their own (in manual mode) ”- they proudly declare. The second group of developers declares as a goal - complete automation of building the school schedule, but in their advertising materials and user manuals they diplomatically keep silent about the achievement of the goal. "Our program can build a schedule in automatic mode, in manual mode and in mixed (semi-automatic) mode" - they state without deceiving users. The attention of potential users to the fact that a horse can drink water from the river, but cannot drink it, and the program can build a schedule in automatic mode, but cannot build it, these developers do not emphasize. In our opinion, this is a very balanced and dignified position, which, despite a little cunning, can only arouse respect. Or, at least, it does not cause aggressive attitudes towards developers on the part of users. And finally, the third group of developers. “Enter the initial data, click the calculation button, and in a few minutes you are guaranteed to receive a schedule with the arrangement of all classes without exception. There are no restrictions on the dimension of the problem. There are at least 99 classes. At least 216 teachers. At least half of the part-time students. Let's divide the class into groups up to at least 256 groups. Restrictions for teachers and subjects are any. Each teacher chooses convenient working days and hours for himself. There are no teachers' windows. Classes in subjects are held only during the hours permitted for these subjects. Strict adherence to parallels. Difficulty points are assigned to each subject. Exact compliance with sanitary standards for the distribution of the total complexity of objects in time is guaranteed. " - they declare without hesitation. By the way, the developers of the most helpless programs in terms of automatic scheduling and also sloppy-looking ones (although there is one that looks very attractive) go to such a simple move. Such programs are aptly dubbed by Microsoft - food dog - "dog food". It is difficult to say what exactly drives people to direct and unsophisticated deception of consumers. This deception always becomes apparent the first time a school's curriculum is introduced into the curriculum. 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 recognized by the court as invalid, while the deceiver returns all the money received to the deceived, compensates the deceived for real damage and, in addition, must transfer the same amount to the state income 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 drawing up a school timetable. For qualified users of a personal computer, who have come to believe in its omnipotence, it seems that the task of drawing up a school timetable is not nearly 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 sciences, not only technical, but also physical and mathematical, not to mention thousands of ordinary lovers of mathematical puzzles, certainly including a large army of students of technical and physical and mathematical education. Among the researchers of the task of drawing up a school timetable, one can also mention two academicians - V.S. Tanaev and V.S. Mikhalevich, one could also name foreign scientists with a worldwide reputation. In addition to scientists, outstanding businessmen did not ignore the task of drawing up a school timetable. And nevertheless, 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 task of scheduling a curriculum. As a confirmation of what has been said, we present a quote from a well-known Russian mathematician. ... Since the task of scheduling is well known to everyone from school life, then on each course there is one or several students, overwhelmed by the idea of algorithmic scheduling of classes. Therefore, I have to warn you that this is a very difficult task. ... There is a special science - the theory of scheduling, 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 observation is interesting. But first, let us give you one more quote. The four-color hypothesis can rightfully be called the “four-color disease”, as it is in many ways similar to the disease. It is highly contagious. Sometimes it is relatively easy, but in some cases it becomes protracted or even threatening. There are no vaccinations against her; 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 lethal outcome has been recorded. There is at least one known case of transmission of the disease from father to son, so it may be hereditary. Here, an outstanding American mathematician sneers at the old problem of painting a political map in four colors, where countries with a common border should 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 took it into his head, to the best of his ability, to track the further career of people who defended their dissertation on the relevant topic. It would seem that the newly established scientist was ordered by "God himself" to convert his scientific achievements into money. That is, to somehow bring your brainchild to the market, since almost always after defending a thesis, there remains a certain program or part of an automated system for scheduling classes. Well, no. All cases of thesis defense on this topic known to the author end with one thing - after defense, the candidate gives up this task and, as a rule, begins (or continues) a teaching career at a university. In other words, it acquires a lifelong, stable immunity to the task of scheduling a curriculum. Finishing the general reasoning about the complexity of solving the problem of drawing up a school timetable, we will refer to two more opinions. But first, let's pay attention to who expresses this opinion. It's no secret that some school computer science teachers, in fits of didactic experiments, instruct schoolchildren as a "homework" to develop a program for scheduling classes for their favorite school. Schoolchildren, naturally, roll up their sleeves with enthusiasm to tackle this problem. As an exhaust from this idea on the Internet, one can find numerous arguments and theorizing on this matter from the above mentioned contingent. What they don't come up with and what opinions are not expressed by Pioneers ... This topic causes no less excitement among people with technical education in attempts to automate the activities of dispatchers of their favorite university. But these opinions, to put it mildly, are of little interest. Professional mathematicians, experts in the theory of timetables, speak about the problem of drawing up a school timetable extremely rarely. Therefore (or even more so) their opinion on this matter seems to be very interesting. So. Sotskov Yuri Nazarovich, Doctor of Phys.-Math. Sci., Professor, Chief Researcher of the Joint Institute for 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 schedule of training sessions is rather difficult, since it belongs to the class of so-called NP-hard problems. ... This article shows how graph vertex coloring can be used to schedule training sessions. ... ... The problem of coloring vertices of a graph is NP-hard, and hence its generalization described in Sec. 2 is also NP-hard. ... Further. Lazarev Alexander Alekseevich, Doctor of Phys.-Math. Sci., Professor, Chief Researcher at the Institute of Management Problems. VA Trapeznikov 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 task of scheduling training is the well-known combinatorial optimization task “Timetabling”. Even finding a feasible schedule is NP-hard in the strong sense of the problem. Therefore, when solving it, it is necessary to use mathematical methods for solving combinatorial optimization problems. ... In short: - "Drain the water, sushi oars, mascara light ..."5 Market for curriculum scheduling software
The curriculum software market, which has evolved along with the market for any software for personal computers, seems to be simply unique, or at least surprising, or at worst very strange. So what is its uniqueness or strangeness? Have you ever seen an advertisement like this: "Buy our vacuum cleaner that cannot suck in dust." Or this: - "All the pans 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 drawing up a school timetable, which cannot compose it, but it can be,” we had to see as much as we wanted. “Well, buy, buy, buy. Our program can create a schedule. She will arrange almost all the activities for you, and the rest, as something herself. Getting out of the dead end is so interesting. Well, at least for $ 15. It's not a lot of money, we worked so much ... ". So how much is a vacuum cleaner that doesn't suck in dust, a leaky pan, or a TV that never shows anything? 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 in the construction of new schools in new development areas. Further, we will make arithmetic calculations using the example of the Russian Federation (after all, the homeland). So, the population is about 140 million people. Thus, there are about 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 is a huge number of schools with the number of students much less than our average figure - 440 people. Obviously, these are schools in rural areas or in very small cities. Hence, a stronger conclusion - a huge number of schools, programs for scheduling classes are not needed in principle. It is, of course, very difficult to estimate the number of schools that do not need such programs in principle. Nevertheless, having carefully looked at the ceiling, we will see a figure there - 70%. From which it follows that 30% of schools have a number of students of 500 or more, and for such schools a program that cannot draw up a school schedule, but can draw up one, would not hurt. We get the final figure - 15 thousand schools. This is, perhaps, the potential market capacity for the Russian Federation. And 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 "vpendyurin free" for all schools in the Russian Federation. The beginning of the development of this program dates back to 1998, and the end (latest version) to 2003. In appearance, especially for its time, the program is certainly not bad. Compared to other similar programs, it has a very logical and well thought-out user interface. In our subjective opinion, the best user interface. However, although there is a button to Create a schedule, 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 cope with. Judging by the reviews on the Internet, almost no one uses this program. So, we will consider it as a "radiation background" that does not affect the general market situation. Let's go further. Let us pose the following question. Are there programs on the market that can provide the head teacher with at least some assistance in scheduling? For example, many head teachers manually schedule a two-step schedule. At the first stage, according to their words: - "Deal with foreigners." In other words, they draw up a timetable for teachers and classes when learning a foreign language. The second stage is everything else. At least two programs on the market, with this, the first stage, cope with envy perfectly. Here you can also plan the time of the elective courses. At the same time, from 10 to 40 percent of the classes are placed. So, of course, there is some benefit 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, she succeeds. The other, while completing the schedule, is absolutely helpless. So how many people use the software for scheduling classes in the Russian Federation today? Some manufacturers of such software publish information about their customers on their websites. True, this information should be treated very carefully. As noted above, some manufacturers in their "marketing fits" go for a very ingenious deception of potential customers. And nevertheless, separating the wheat from the chaff, we get the figure - about 1500 schools. Which is about 10% of the potential market capacity. Consequently, 90% of potential customers have not yet been hired. Now let's turn our attention to the world market. As follows from the previous calculations, a very convenient way to calculate the number of leads is this way. We take the population of the country, discard four zeros, and get the number of potential customers. So let's do it. Europe - 500 million people. USA - 300 million people. Canada - 30 million Japan - 125 million Australia - 20 million Other developed countries - 25 million people. Here it is - the "Golden Billion". We discard four zeros. We get - 100 thousand potential customers. Now the question is, "How many schools out of this golden billion use school timetable software?" We use the same technique, separating the wheat from the chaff, as for the Russian Federation. We get the figure - about 30 thousand schools. Which is 30% of the market. At the same time, 70% are open to aggressive marketing (hilling). Now it remains to translate quantity into quality. That is, multiply the number of potential customers by the price of one software license. In other words, to estimate the capacity of the world market in US rubles. But for this you need to know the price of such a license. I wonder if the reader had to hold in his hands a thick book with something like this title: - "The cost of software." And we had to. In fact, the formula is very simple. Software, no matter how complex and volume 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 labor, talent, knowledge, etc., landing a person on the moon, in comparison with this operating system, is childish pranks. And yet, a hundred and fifty bucks per barrel, and you're a legal user. The only problem is that the number of potential customers - users of the operating system and the program for drawing up the school timetable is not comparable, neither in the first nor in the second approximation. Hence the conclusion: - "Despite the fact that some ask for 15 dollars for leaky pans, a program that could really solve most of the problems of head teachers, should be expensive." It remains only to answer the question: - "What is expensive?" Of course, everyone has their own ideas about "Expensive". But probably, for the head teacher (or a similar position, if we are talking about the world market), his monthly salary is expensive. That is, from $ 1,000 to $ 5,000. That, in fact, we observe, or at least previously observed, in reality. At first, these programs cost exactly that much on the world market. The fall in prices, as it seems to us, happened precisely because of what was suddenly revealed - a leaky saucepan was bought for $ 5,000. And finally, multiplying the quantity by the price, we get the approximate size of the world market for school timetable software - from 100 to 500 million US dollars. That is, the market is no less money-intensive than, say, the market for various computer-aided design systems in industry and construction. And by the way, it is no less science-intensive.6 "Ancient Egyptian" algorithm for solving the problem
In the spring of 2012, an archaeological scientist turned to familiar programmers with a strange request. From his words, when decrypting ancient Egyptian manuscripts, he came across a description of the algorithm for drawing up 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 building a school schedule. At first, his friends made fun of him. But after carefully reading the strange records, we decided to check them out. So, we proceed to describe the idea of this algorithm, in fact, to a summary of the translation of an ancient manuscript. We will preliminarily 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 and familiar terminology for a person living now. 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, while 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 applied. It should be noted that each separately of the problems that are sequentially solved in the course of the algorithm is not NP-hard (not solvable). This allows, with the help of a sequential solution of a series of easily solvable problems, to solve the entire problem of drawing up a school timetable as a whole. In the first step you should choose the mode of operation of the educational institution, namely, decide on how many days a week the school will work (5 or 6) and decide on the number of lessons held per school day (7 or 6, respectively). You also need to set the number of classes of students in the school. Next, you need to put bans on those hours for which lessons are not held. These are the last hours of each school day. For the lower grades (in our terminology, this is starting from the 5th) there are more such prohibitions, for the middle grades there are fewer, and for the oldest (11th grades) these prohibitions are absent altogether. Which meets our sanitary standards. The table of prohibitions on conducting lessons, which will be further used throughout the entire algorithm, is remembered. In the second step a schedule for part-time workers is being built. It turned out that the ancient Egyptian educational institutions did not disdain the work of part-time workers. The main feature of this task is that part-time workers are allowed to declare in an ultimatum the days on which they will work. In addition, some part-time workers are allowed to refuse work during 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 a prescribed coloring algorithm for vertices of an ordinary graph. You can get acquainted with this mathematical model in detail with the help of the already mentioned article or with the help of other numerous journal articles, for example, [,], as well as getting acquainted with the books [,]. Further, for each lesson (class, teacher, time), using the algorithm for solving the assignment problem, a room is selected for conducting this lesson. The algorithm for solving the assignment problem is described in many modern textbooks, in particular, you can get acquainted with it from the book. The end of the second step is an operation to combine the table of prohibitions for 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 teaching lessons, which will be one of the restrictions for the next step of the algorithm. Third step consists of solving the problem of conducting classes of the students' choice (in our terminology of elective courses). A feature of this task is that a certain number of classes, at a certain academic hour, are combined into streams, so that then at this 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 is finally built. That is, at this step, teachers are not assigned to conduct elective courses. When building the schedule, the rule is observed - for any stream in one school day, no more than one academic hour can be assigned to conduct an elective course. In addition, another rule is observed - at any given time, elective courses cannot be scheduled for more than one stream. This rule (limitation) seems to be 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 when several streams at the same time require a large number of free premises. The premises for conducting elective courses, at this step, just as the teachers are not selected, they will be selected together with the teachers after the entire schedule has been built. The algorithm for solving the problem of conducting elective courses is the algorithm for the prescribed coloring of the vertex of an ordinary graph, which we indicated in the description of the previous step. The new table of prohibitions on conducting lessons is built in the same way as in the previous step. The resulting schedule is combined with the ban table. In the fourth step algorithm to build a schedule for foreign language lessons. The peculiarity of this task is that the class can be divided into groups. Teachers cannot declare in an ultimatum order what days they will work. However, for teachers with a small workload, one or two days off are guaranteed, which they will be given. Just like in the second step of the algorithm, some teachers teaching a foreign language may require them to be exempted from lessons during the first hour of the working day when they work. The problem of scheduling teachers / classes for learning a foreign language, just like in the second and third steps, is solved using the algorithm for the prescribed coloring of the vertices of an ordinary graph. In the same way as in the second step, using the 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 to combine the prohibition table for lessons with the resulting schedule. Thus, we get a new version of this table, which we will use in the sixth step. After the completion of the 4th step of the algorithm, depending on the curriculum of the school, usually from 15% to 40% of the entire teaching load provided for by this plan is allocated. In the fifth step the load determined by the curriculum is calculated, for premises that are in short supply for the school. Such premises, as a rule, are gyms, workshops for conducting labor (technology) lessons, classrooms equipped with computers for conducting informatics lessons. This calculation is carried out with the aim of the maximum possible load (minimum "downtime") of such premises. In the sixth step a schedule is built for all the remaining subjects except for those held in scarce premises. Teachers do not have the opportunity to state an ultimatum about which days they will work, but for those teachers who have a low workload, one or two days off are guaranteed, and for some teachers there is an opportunity to refuse to work in the first lesson. This problem is solved using an algorithm for the prescribed coloring of the edges of a bipartite multigraph. You can get acquainted with the idea of this algorithm from the book or from journal articles [,,,,]. The constructed schedule consists of fours - class, teacher, subject, time. At the same step, all fours, using the algorithm for solving the assignment problem, are compared to the premises where these classes will be held (fours). After completing this step, the entire schedule grid is filled, with the exception of classes held in scarce premises. However, the remaining "holes" in the schedule, this is the schedule for conducting classes in hard-to-find premises. Thus, we can assume that at this - the sixth step, in a sense, two schedules are simultaneously built - for ordinary teachers / classes and for scarce premises / classes. At the seventh step the division of classes into groups of subjects is carried out, which will be held in scarce premises. As a rule, in such subjects as physical education, labor (technology), computer science classes are divided into groups. If the set of teachers for whom the schedule was built in the previous step intersects with many teachers conducting classes in scarce premises, then a table is formed for the forbidden hours of work of teachers, which are the intersection of these sets. Using the algorithm for solving the assignment problem, the selection of teachers for each group is carried out. The last step is the eighth. 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 was reserved for them in step 3 of the algorithm. And if this teacher is able to recruit a group of students, then he will independently put his elective course in the schedule, along with the premises he himself has selected. The general rule for all the previously described steps, except for the fifth, is the rule - each class in one day cannot have more than one lesson in any subject. In addition, it is a general rule for teachers that each teacher can teach classes in several subjects, including one class.7 Algorithm testing
As you can see from the previous section, there is nothing difficult to understand in the work of the algorithm for constructing the school timetable. One after another, interconnected, separate, easily solvable (not NP-hard) problems are solved until all of them are exhausted. Nevertheless, there was no reason to assert with confidence that each of these tasks could be solved. In the absence of any theoretical substantiation of the algorithm, it was possible to test its performance only experimentally, especially since it was precisely such a task that was posed by an archaeological scientist who stumbled upon an ancient manuscript and made its translation. It is quite natural that the first thought that occurred to programmers was to create a common application for the Windows operating system. But what is a typical win application? When activated (launched for execution), it waits for events from the user, for example, input of initial data. And how can this initial data be obtained and later entered into the program? Thank God, or rather the United States, at present, a somewhat self-respecting school has opened its website on the Internet and the first thing that appears on this website, apart from photos from various festive events, is the school's curriculum. It remains only to copy it and enter it into the program as the initial data for calculating the schedule. Question. How long does it take for this? The practice of using the school timetable programs currently offered by the market has shown that to enter the curriculum together with the formation of the table of distribution of the teaching load, it takes from 8 to 10 hours, to put it mildly, painstaking work. Suppose that this curriculum has been introduced, and the pedagogical load distribution table has been formed, and lo and behold ... the schedule has been built. What does it say. Absolutely nothing. There is no guarantee that the next task will be solved. Now, if the schedule had not been built, it would say a lot, namely, that the algorithm does not solve the problem. In other words, a typical win application is, in a sense, almost impossible to test. How to be? Again - thank God, or rather, thank Microsoft, the so-called console application mode is supported in modern versions of the Windows operating system. By the way, for some young people this is a complete revelation, they have never seen black windows with lines of text running inside these windows. Indeed, this is the style of mainframes from the distant past and long gone from the scene - MS-DOS. But these windows have one advantage. They can hang on a computer screen, making the necessary calculations, without any human intervention, both day and month, and ... I can't say how much. This is exactly what was required to test the algorithm. Further, the line of reasoning was as follows. Writing a generator of initial data (roughly speaking, the curriculum of a typical school and a table of distribution of the pedagogical load) of course will take some time, but, once written, it will allow you to get an unlimited number of test tasks to test the algorithm, it will be enough only after solving the next tasks to transfer control to this generator to build a new (next) task. It will be possible to obtain statistically reliable data on the quality of the tested algorithm. For example, 80 percent of the tasks 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 was to be done - a console application, this was the way out of this situation. As the saying goes, a fairy tale tells itself quickly, but it is not done quickly. It turned out to be not such an easy task to come up with a generator of initial data that adequately reflects all practical situations, even of a typical school. But once crazy dreams came true ... sooner or later ... how long the rope doesn’t hang ... The generator of initial data is finished, the ancient Egyptian algorithm is programmed, “all errors are corrected”, traps for errors are set, checks of calculation results are installed. At the beginning of the program, a small number of classes were proposed for scheduling - from 9 to 14 (small school). Solutions popped out like a machine gun. With an increase in the number of classes - from 15 to 21 (high school), decisions were fired quickly, but not like a machine gun ... more like a pistol. Further. Here it is ... a big school, up to four grades in parallel, the total number of grades is from 22 to 28. The brakes are clearly on ... The process began to resemble a lazy duck waddling from foot to foot. But one thing pleased me - 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 were required. And for a dozen computers (you can estimate the amount of heat emitted 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. As a result, after a year of "violent actions" of the ancient Egyptian algorithm in relation to the venerable four-core seven, and after tens of millions of solved problems, we can confidently assert: be solved without human intervention in a fully automatic mode. " At the same time, the total calculation time for 1000 tasks is approximately the following: for a group of tasks from 9 to 14 classes = 20 minutes, for a group of tasks from 15 to 21 classes = 40 minutes, for a group of tasks 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's experiment on checking (testing) the algorithm for drawing up a school timetable in a fully automatic mode, without the participation of a person, for whom tens of millions of test tasks were solved, was successfully completed. For almost all test tasks (initial data), a schedule was fully constructed that satisfies all the constraints.8 The logical model of the future software
After the completion of the annual testing of the algorithm for drawing up the school timetable, the question arose: - "So what next?" First of all, it is striking that the console application will not be able to convince anyone that the task of drawing up a school timetable is really being solved ... unless the programmer himself who wrote this application. Create a black window, with lines like this appearing from time to time there: - "The number of solved problems = 12547564" to support even a poorly performing fifth-grader. Thus, a normal person simply will not believe such, if I may say so, a program, and will do the right thing. It is impossible to do without a full-fledged win-application. But, at first, it would not be bad, it will be determined with the goals of creating such an application. At least two such goals are in sight. This is the creation of full-fledged software with all the ensuing consequences, and - the creation of an application that demonstrates the operation of the algorithm, which is worse or better able to convince a person that he is not being deceived. And the hedgehog understands that in terms of labor intensity, these two projects are simply not comparable. Quite naturally, the decision was made to take the easy path. Good: - "What is required of such a win-application - demo?". Before we can even put another question: - "What should it be?" Firstly. The headache about a convenient, understandable, practical and beautiful user interface is immediately removed. For such a demonstration, a very primitive interface is quite enough. It is only important that the user can see the initial data that are offered to the program for the calculation (naturally generated randomly) and the results of this calculation. At least theoretically, the user will be able to check the correspondence of the initial data and the result obtained using the program. Is such a check difficult? ... The answer is unequivocal: - "Yes, it is not simple ...". Especially if you know how many traps and checks are contained in the console application for constant verification of the results obtained, as well as the size of the code of these checks and traps. Are there other ways of persuasion? ... Perhaps, passing on to everyone interested ... the source code of the program. But, for example, in Microsoft it is not accepted. Secondly. The problem of the help file, user manual, and other bows and bells and whistles absolutely necessary for a full-fledged software is removed. And so they did. On the main form of the application, more than twenty buttons were stuck, of which only one is active at each stage of the calculation, not counting the buttons of the type - About the program, Start a new task, Close me. Click on this button, a window appears with the Generate data button. You press Generate data, the constructed data appears in the window on a white background. We close the window. The button that was just pressed goes out (ceases to be active), the next one that should be pressed becomes active. We press. The next window opens. And there is the button Build a schedule. Click on Build schedule, the built schedule appears. Anyone can check whether the schedule is correct or not. And so on until all the steps of the algorithm have been passed. And then you can click on the big button Start new task. And so in a circle. Or click the Close me button. At first glance, it may seem: - "This whole demo program is a monkey's work." But this is not the case. For at least three reasons. Firstly. During the development of the demonstration, a rather important task of developing the future architecture of a full-fledged software was solved. Namely. It was required to separate the "brains" from the "torso" in the most severe way. To put it more clearly, separate the scheduling algorithm code from the source data generator code and the user interface code. All the code of the algorithm for calculating the schedule is concentrated in the dynamic link library, so the user interface, like a client, can handle tasks to the dynamic library, which acts as a server, to build various schedules compiled at different steps of the algorithm. This will allow in the future, without touching the schedule calculation algorithm code, to experiment with various interface options until users are completely and completely satisfied. Secondly. Despite its primitiveness, the demo user interface is a logical model of the future of a convenient, understandable, practical and beautiful user interface. For example, it implements the ability to return to the previous step of the algorithm, and this feature, in turn, influenced the data structure of the program. In addition, the demo interface supports such a feature of the algorithm as moving from step to step in a strict sequence, which ensures data integrity and protection from incorrect changes. Thirdly. Again, we repeat, despite its primitiveness, the existing user interface is suitable for analyzing a mathematical model of practical situations that arise when drawing up a school timetable adopted in this program. Such an analysis or examination could be carried out by specialists who are well familiar 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 will have such a desire), but due to the general mathematical culture obtained, 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 by various kinds of publications. "So what's next?" And then the development of full-fledged software in accordance with all the laws and rules of software engineering, which now, in terms of complexity, does not exceed the usual software for ERP systems. Just don’t ask: “How long will it take and what is the complexity of developing such software? ...”. And all the more, do not ask: - "How much will such a development cost? ...".9 Problems with the business model
As previously estimated, the global market for fully automated school timetable software is between US $ 100 million and US $ 500 million. However, this market, as venture capitalists say, still needs to be “raised”. And here, at least two problems emerge quite clearly. One problem is: - "Expensive". We have already stopped at it. And another, in our opinion more serious, is: - "Reputation of such software". To use a metaphor, the reputation of such software resembles a crap, heavily manured and smoking garbage dump after the battle on Kulikovo Field. Moreover, the smoke is so pungent that you want to close your eyes and stop breathing. As mentioned earlier, when talking to potential school timetable software clients, that conversation easily turns into swearing. "We got it ... with your automation, the information space of the school and electronic diaries, let me work in peace ...". What can be done to change the reputation of such software and the attitude of the head teacher towards it from hostile, to at least neutral? We do not stutter about a positive image yet. About ten years ago, it was still possible to say that computers in the offices of head teachers are for furniture, as an indispensable accessory for scholarship and progressiveness. At best, a computer is used instead of a typewriter (although, as noted earlier, it was this very circumstance that served such a rapid flourishing of the personal computer industry). The situation has now changed. Many have already tried ... We have just discussed the results of such tests. It remains to start everything from the beginning. Namely. With a business model for the distribution of such programs. Even without looking closely, you can see that this business model has remained virtually unchanged over the past 15 years. Find the website of the program, download the demo version, issue an invoice for payment ... Everything seems to be clear with the invoice for payment. You can't do without the website of the program either. But what about the demos? And with demo versions everything is different. Option one. Our demo version is no different from the working version of the program, only you cannot save the entered data, and you cannot print the obtained results to the printer. And so, everything works. Is it possible with the help of such a demo version to evaluate all the advantages and disadvantages of the program? As already noted earlier, to enter all the initial data, so that there would not be a squeaky gundel about an hour, a maximum of one and a half, in reality, at least 8 - 10 hours of continuous and painstaking (to hellish boring) work is required. A normal person, and even more so a user who starts working with the program for the first time, when he needs to simultaneously learn to work with the program and accurately, without errors, enter a mountain of initial data, at one time he will not be able to do this. It takes at least two or even three days (times). Now imagine the fear of a beginner that the power will be cut off or something will reboot. Well ... a normal person would not want 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 often happens, with bitterness for the wasted time, press the Del key. To be fair, it should be noted that the same developers came up with another option. We made a "breaker" for our program. An unsuspecting, good-natured user, having previously disabled his conscience with a small key, downloads an illegal copy (deme + breaker). Installs, breaks, and ... everything works ... As they say, use it for health ... True, after about half a year, the program will announce to you that it is entering demo mode, and to save your data, be so kind. .., ask the developer for an account statement ... Looking at such tricks from the outside, this option seems - in the end, more honest. Although, of course, the user is trying to deceive the manufacturer, the manufacturer is deceiving the user ... by the way, promising him that in a few minutes after entering all the initial data, he will receive a ready-made schedule. It is safe to say that the vast majority of users will never know that their data was exposed to a real threat. After spending 15 - 20 hours working with the program and making sure of its uselessness, shouting: - "All programs, like men, such ...", potential buyers angrily remove this program from their computer. And after an hour or an hour and a half, calming down, catching their breath, they say to themselves: “What am I? .. all the same smart that she didn’t pay money for it ..., 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've seen yours, if I may say so, the program. And he introduced that, nothing at all - four classes. And she told me: - "I can not make a schedule." You can put it in yourself ... Damned speculators. " Here we are faced with a case when the developers found adventures on their "... (head)". Those who think that scheduling a school with four grades is much easier than, for example, twenty, are deeply mistaken. That is why, when testing the "Ancient Egyptian" scheduling algorithm, it was decided - when generating test data, for a minimum of the number of classes, choose the number - nine. This is sometimes explained by the impossibility of automatically compiling a table of the distribution of the teaching load. Simply put, to distribute the load between a meager number of classes and, accordingly, a meager number of teachers. Apparently, such tricks can only be shown by a very experienced hand (or eye, if you like) of a person. Option three. Oh well. Use our program. But, two weeks. And in two weeks everything, the Sabbath. "We'll turn off the water ..." Is it possible to master the program in two weeks and evaluate all its advantages and disadvantages? In all honesty, let's say: - "Perhaps, what is possible ...". But on one condition. You need to stop doing everything else. And the favorite word of the head teacher: - "Busy". “Oh, busy. So busy, that neither to breathe, nor ... there is no time. " Will the head teacher leave everything in the world for two weeks and plunge into the program for scheduling for this period? As scientists say: - "It's hard to say ...". In short, everything is bad ... And so bad, and so not convenient ... Where to look for a way out? Maybe rent?10 SaaS software business model
Initially, the entire computer industry used a rental business model - the first computers cost a lot of money and their computing power was leased to customers. With the advent of the Internet, the old business model was revived, but on a fundamentally different technological basis. SaaS(eng. software as a service - software as a service) - a business model for the sale and use of software, in which the supplier develops a web application and independently manages it, providing the customer with access to the software over the Internet.
The main difference between SaaS and the old model is that in the past, customers accessed computers directly, rather than using wide area networks. Since the SaaS model is focused on the provision of services using 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 saves potential customers from risking a relatively large sum of money when paying for a software product from a group of products with an almost hopelessly damaged reputation. Using a rental business model, the customer will be able to calmly and gradually make sure that the offered product, he really needs, and that his expectations from the use of the product coincide with what he actually receives. Earlier we spoke in sufficient detail about the expectations of the head teachers from this kind of programs.
11 Instead of a conclusion
Sometimes, some with a sarcastic voice ask: - "Do you have a business plan? ..." Yes. And yet, very simple. "To consistently solve emerging problems as they come ...". As a last resort, you can use the SaaS model (business plan - on demand). If anyone needs it, it will be possible to plan everything in detail and in detail, no accountant will pick on!
Bibliography
Baltak S.V., Sotskov Yu.N. Scheduling training sessions based on the coloring of the vertices of the graph. Informatika, 2006, no. 3, p. 58 - 69. Borodin O.V. Colorings and topological representations of graphs // Discrete Analysis and Operations Research. 1996, Volume 3, No. 4, p. 3 - 27. Borodin O.V. Generalization of Kotzig's theorem and prescribed coloring of edges of plane graphs // Matematicheskie zametki. 1990, Volume 48, Issue 6, p. 22 - 28. Vizing V.G. Coloring of vertices of a graph under majority constraints on the colors used // Discrete Analysis and Operations Research. 2009, Volume 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 of optimization in the preparation of the curriculum // New information technologies in education. Collection of scientific papers. - M .: 1C-Publishing, 2013, Part 2, p. 51 - 55. Gary M., Johnson D. Computing machines and intractable problems. - M .: Mir, 1982 .-- 416 p. Distel R. Theory of graphs: Per. from English - Novosibirsk: Publishing house of the Institute of Mathematics, 2002 .-- 336 p. Emelichev V.A., Melnikov A.I., Sarvanov V.I., Tyshkevich R.I. Lectures on graph theory. - M .: Science. Ch. ed. physical-mat. lit., 1990 .-- 384 p. Ichbana D., Knepper S. Bill Gates and the Creation of Microsoft. - Rostov-on-Don: Phoenix Publishing House, 1997. - 352 p. Karpov D.V. Dynamic regular colorings of graph vertices. // Notes of scientific seminars POMI. 2010, Volume 381, p. 47 - 77. Magomedov A.M., Magomedov T.A. A regular 5-edge coloring of a bipartite graph, interval on one part, // Applied discrete mathematics. 2011.No. 3 (13), p. 85 - 91. Papadimitru H., Steiglitz K. Combinatorial optimization. Algorithms and complexity. Per. from English - M .: Mir, 1985 .-- 512 p. Romanovsky I.V. Discrete analysis. Study guide for students specializing in applied mathematics and computer science. - Edition 2, revised. - SPb .: Nevsky dialect, 2000 .-- 240 p. Swami M., Thulasiraman K. Graphs, networks and algorithms: Per. from English - M .: Mir, 1984 .-- 455 p. Smirnov V.V. Pererburg schools and school buildings. The history of school construction in St. Petersburg - Petrograd - Leningrad 1703 - 2003 - SPb .: Publishing house "Russian-Baltic information center" BLITZ ", 2003. - 144 p. Stetsenko O.P. On one form of coloring the edges of a graph in prescribed colors // Discrete Mathematics. 1997. Volume 9, Issue 4, 92 - 93. Urnov V.A. Schedule is the most demanded AWP 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-703Links:
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 peeping" on the part of the sworn enemies of Soviet power. The very task of drawing up an educational schedule (without the help of computers) is, most likely, not less than three hundred years old. Cases have been recorded when the head teachers - in general, cultured and well-mannered people, having heard the phrase: - "Program for drawing up a school timetable" instantly switched to mother tongue. Here we will not dwell on the theory of NP-hard problems, since a discussion of this issue would lead the reader far away from the topic of interest to us, and would also be clearly premature and superficial. The interested reader can be recommended to refer to perhaps the most cited publication on this topic in our country. For a complete understanding of 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 compared to English-language publications. Most likely, their number does not exceed the total contribution of the Russian Federation in the field of high technologies, which is estimated in the range of 0.4 - 0.6% (from zero point four tenths of a percent to zero point six tenths of a percent) of the global total. True, there are an order of magnitude less physical and mathematical sciences. Tanaev Vyacheslav Sergeevich (1940 - 2002) - Belarusian mathematician, director of the Research and Development Institute "Cybernetics" of the National Academy of Sciences of the Republic of Bashkortostan, Doctor of Physical and Mathematical Sciences (1978), professor (1980), full member of the National Academy of Sciences of Belarus (2000). Research 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 decisions, systems analysis, theoretical and economic cybernetics. USSR State Prize (1981). However, the transfer of 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.
This will not happen in any way.
Fate is envious, 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.