[go: up one dir, main page]

CN111161112A - Administrative class intelligent class scheduling method, system, computer equipment and storage medium - Google Patents

Administrative class intelligent class scheduling method, system, computer equipment and storage medium Download PDF

Info

Publication number
CN111161112A
CN111161112A CN201911374006.4A CN201911374006A CN111161112A CN 111161112 A CN111161112 A CN 111161112A CN 201911374006 A CN201911374006 A CN 201911374006A CN 111161112 A CN111161112 A CN 111161112A
Authority
CN
China
Prior art keywords
class
schedule
classes
administrative
subjects
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201911374006.4A
Other languages
Chinese (zh)
Other versions
CN111161112B (en
Inventor
杜振锋
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Guangdong Yijiaotong Technology Co ltd
Original Assignee
Guangdong Etonedu Co ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Guangdong Etonedu Co ltd filed Critical Guangdong Etonedu Co ltd
Priority to CN201911374006.4A priority Critical patent/CN111161112B/en
Publication of CN111161112A publication Critical patent/CN111161112A/en
Application granted granted Critical
Publication of CN111161112B publication Critical patent/CN111161112B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/10—Services
    • G06Q50/20—Education
    • G06Q50/205—Education administration or guidance
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/12—Computing arrangements based on biological models using genetic models
    • G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Business, Economics & Management (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Theoretical Computer Science (AREA)
  • Biophysics (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Evolutionary Biology (AREA)
  • Tourism & Hospitality (AREA)
  • Strategic Management (AREA)
  • Educational Technology (AREA)
  • Educational Administration (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • General Physics & Mathematics (AREA)
  • General Health & Medical Sciences (AREA)
  • Physiology (AREA)
  • Biomedical Technology (AREA)
  • General Engineering & Computer Science (AREA)
  • Molecular Biology (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Evolutionary Computation (AREA)
  • Data Mining & Analysis (AREA)
  • Computational Linguistics (AREA)
  • Computing Systems (AREA)
  • Artificial Intelligence (AREA)
  • Genetics & Genomics (AREA)
  • Economics (AREA)
  • Human Resources & Organizations (AREA)
  • Marketing (AREA)
  • Primary Health Care (AREA)
  • General Business, Economics & Management (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

The invention discloses an intelligent course scheduling method, a system, computer equipment and a storage medium for administrative classes, wherein the method comprises the following steps: reading a teaching plan; pre-arrangement courses are sequentially carried out on the fixed subject to be arranged and the administrative course subject; generating a plurality of initial class schedules according to the pre-arrangement result; calculating the population fitness values of a plurality of initial school timetables by adopting a genetic algorithm, and selecting the initial school timetable with the minimum population fitness value as an optimal school timetable; judging whether the population fitness value of the optimal class schedule reaches a preset expected value or not; if the population fitness value of the optimal class schedule reaches a preset expected value, outputting the optimal class schedule; and if the population fitness value of the optimal class schedule does not reach the preset expected value, sequentially crossing and mutating the optimal class schedule, reselecting the optimal class schedule, returning to judge whether the population fitness value of the optimal class schedule reaches the preset expected value or not, and executing subsequent operation. The invention utilizes the strong computing power of the computer and the intelligent algorithm to overcome the difficulty of manually arranging the school timetable in the prior art.

Description

Intelligent course scheduling method and system for administrative classes, computer equipment and storage medium
Technical Field
The invention relates to an intelligent course arrangement method, system, computer equipment and storage medium for administrative classes, and belongs to the field of course arrangement in education.
Background
The course arrangement problem is a multi-target and multi-constraint optimization decision problem and is an NP combination optimization problem. Due to these characteristics of course arrangement, course arrangement is a difficult point in the work of teaching affairs management.
The traditional manual arrangement mode of the school timetable not only needs to consume a large amount of time of workers, but also is not suitable for adjustment of the discharged school timetable, and simultaneously is difficult to meet the requirement of more humanization on teachers and students under the condition of limited educational resources. Although the problem of course arrangement has been a research topic of many software companies since a long time ago, the technology is really mature, can solve the constraints in many aspects such as teachers, classrooms, laboratories, sports grounds, course distribution, time distribution, dividing and combining work, single and double weeks, requirements of teachers and the like, and can arrange courses for a plurality of class schedules at the same time is few.
In recent years, scholars at home and abroad apply different algorithms to solve the course scheduling problem, such as an ant colony algorithm, a simulated annealing algorithm, a greedy algorithm and the like, but on one hand, the methods have certain defects, for example: the consideration is insufficient on the constraint condition of course arrangement problems, and the problem of simultaneous course arrangement in multiple grades is difficult to solve.
Disclosure of Invention
In view of the above, the present invention provides an intelligent class scheduling method, system, computer device and storage medium for executive class, which utilizes a computer to release manual class scheduling time, and utilizes the strong computing power of the computer and an intelligent algorithm to overcome the difficulty of traditional manual class schedule arrangement and solve the current class scheduling problem.
The invention aims to provide an intelligent class scheduling method for administrative classes.
The second purpose of the invention is to provide an intelligent course arrangement system for administrative classes.
It is a third object of the invention to provide a computer apparatus.
It is a fourth object of the present invention to provide a storage medium.
The first purpose of the invention can be achieved by adopting the following technical scheme:
an intelligent executive class scheduling method, comprising:
reading a teaching plan;
according to the teaching plan, pre-arrangement courses are sequentially carried out on fixed subjects to be arranged and administrative course subjects;
generating a plurality of initial class schedules according to the pre-arrangement result; the initial class schedule comprises a first time slot, a second time slot, a third time slot and a fourth time slot, wherein the first time slot is a time slot, and the first time slot is a time slot of each class;
calculating the population fitness values of a plurality of initial school timetables by adopting a genetic algorithm, and selecting the initial school timetable with the minimum population fitness value as an optimal school timetable;
judging whether the population fitness value of the optimal class schedule reaches a preset expected value or not;
if the population fitness value of the optimal class schedule reaches a preset expected value, outputting the optimal class schedule;
and if the population fitness value of the optimal class schedule does not reach the preset expected value, sequentially crossing and mutating the optimal class schedule, reselecting the optimal class schedule, returning to judge whether the population fitness value of the optimal class schedule reaches the preset expected value or not, and executing subsequent operation.
Further, according to the teaching plan, the fixed subject to be arranged and the administrative course subject are arranged in advance in sequence, and the method specifically comprises the following steps:
calculating the number of courses per week of each class according to the teaching plan;
dividing each week into a plurality of time periods, and respectively taking each time period and each class as a head column and a head row of a school timetable;
the subject to be ranked is fixed in all classes for course ranking;
from the first class, the administrative course subjects are arranged from the first time slot of each week to the next, and the first class arrangement is completed;
starting from the next class, and arranging the administrative course subjects from the position of no course arrangement from top to bottom;
judging whether the names of teachers with the same department appear in other classes in the same row, if so, jumping to the final position where the courses are not arranged, and arranging the courses from bottom to top; if the conflict still occurs, the course is arranged to the previous vacant position; if all the vacant positions have conflicts, selecting the scheduled class positions for replacement, and meeting the requirement that no conflicts occur after replacement;
judging whether all classes are arranged, if so, finishing the pre-arrangement of the classes; otherwise, returning to the next class, and arranging the administrative course subjects from the position of the non-arranged course from top to bottom and executing the subsequent operation.
Further, the population fitness value is calculated by using a fitness function, where the fitness function is as follows:
Figure BDA0002340422150000021
wherein, ω isiThe weight of each fitness function, the size of which is determined by the priority of the user's needs, fiA fitness evaluation function for each user requirement, as follows:
Figure BDA0002340422150000031
wherein N isiTo violate the number of conflicts in the class schedule against user demand i,
Figure BDA0002340422150000032
is a penalty factor.
Further, the user requirements comprise physical constraints, fixed discharge, forbidden discharge, optimal discharge, intra-week dispersion and intra-day concentration;
the physical constraints are: the teacher can only go to the previous course in the same time period;
the row fixing means that: arranging fixed subjects in fixed time periods;
the banning refers to: forbidding teachers from being scheduled for lessons in the time periods without the schedule;
the optimal ranking means that: arranging a specified subject in a specified time period;
the said dispersion in week means: courses are arranged uniformly in one week;
the intra-day concentration refers to: the teacher's lessons are collectively arranged for a certain time period in the morning or afternoon of the day.
Further, the optimal class schedule is crossed, and the method specifically comprises the following steps:
randomly selecting courses at two positions in a certain column in the optimal class schedule for exchange;
and after the courses of the two positions are exchanged, judging whether a conflict of violating physical constraints is generated, and if so, canceling the cross operation.
Further, the method for changing the crossed optimal class schedules specifically comprises the following steps:
if the crossed optimal class schedule is the class schedule of a single grade, exchanging two lines of the class schedule of the single grade;
if the crossed optimal schedules are schedules in multiple grades, dividing the schedules in the multiple grades into different grades, and randomly interchanging two lines in a certain grade;
and after the two rows of a certain grade are exchanged, judging whether conflict of violating physical constraints occurs, and if so, cancelling the mutation operation.
The second purpose of the invention can be achieved by adopting the following technical scheme:
an intelligent course scheduling system for administrative classes, the system comprising:
the reading module is used for reading the teaching plan;
the pre-course arrangement module is used for sequentially pre-arranging courses for fixed subjects to be arranged and administrative courses according to the teaching plan;
the generating module is used for generating a plurality of initial class schedules according to the pre-arrangement class result; the initial class schedule comprises a first time slot, a second time slot, a third time slot and a fourth time slot, wherein the first time slot is a time slot, and the first time slot is a time slot of each class;
the selection module is used for calculating the population fitness values of a plurality of initial school timetables by adopting a genetic algorithm, and selecting the initial school timetable with the minimum population fitness value as the optimal school timetable;
the judging module is used for judging whether the population fitness value of the optimal class schedule reaches a preset expected value or not;
the output module is used for outputting the optimal class schedule if the population fitness value of the optimal class schedule reaches a preset expected value;
and the cross variation module is used for sequentially crossing and varying the optimal class schedule if the population fitness value of the optimal class schedule does not reach the preset expected value, reselecting the optimal class schedule, returning to judge whether the population fitness value of the optimal class schedule reaches the preset expected value or not, and executing subsequent operation.
Further, the pre-lesson scheduling module specifically includes:
the calculating unit is used for calculating the number of courses per week of each class according to the teaching plan;
the dividing unit is used for dividing each week into a plurality of time periods, and taking each time period and each class as the head line and the head line of the school timetable respectively;
the first course arrangement unit is used for arranging courses of the subjects to be arranged fixedly in all classes;
the second course arrangement unit is used for arranging the subjects of the administrative courses from the first time period of each week to the next from the first class to finish the course arrangement of the first class;
the third course arrangement unit is used for arranging the subjects of the administrative courses from the position of the next class from top to bottom;
the first judging unit is used for judging whether the names of teachers with the same department appear in other classes in the same row or not, if yes, conflict occurs, the teachers jump to the last position where the class is not arranged, and the class is arranged from bottom to top; if the conflict still occurs, the course is arranged to the previous vacant position; if all the vacant positions have conflicts, selecting the scheduled class positions for replacement, and meeting the requirement that no conflicts occur after replacement;
the second judgment unit is used for judging whether all classes are arranged, and if so, finishing the pre-arrangement course; otherwise, returning to the next class, and arranging the administrative course subjects from the position of the non-arranged course from top to bottom and executing the subsequent operation.
The third purpose of the invention can be achieved by adopting the following technical scheme:
a computer device comprises a processor and a memory for storing a program executable by the processor, wherein when the processor executes the program stored in the memory, the intelligent class scheduling method for the administrative shift is realized.
The fourth purpose of the invention can be achieved by adopting the following technical scheme:
a storage medium stores a program, and when the program is executed by a processor, the intelligent class scheduling method for the administrative classes is realized.
Compared with the prior art, the invention has the following beneficial effects:
1. according to a teaching plan, subjects to be scheduled and administrative classes are fixed and are subjected to pre-scheduling in sequence, a plurality of initial school timetables are generated according to a pre-scheduling result, a genetic algorithm is adopted to calculate the population fitness values of the initial school timetables, the initial school timetable with the minimum population fitness value is selected as an optimal school timetable, if the population fitness value of the optimal school timetable reaches a preset expected value, the optimal school timetable is output, if the population fitness value of the optimal school timetable does not reach the preset expected value, the optimal school timetable is crossed and mutated in sequence, then the optimal school timetable is selected again until the population fitness value reaches the preset expected value, the genetic process is carried out towards a predicted direction, convergence can be faster, and actual tests show that the scheduled school timetable can meet the actual requirements of the administrative class scheduling of middle and primary schools.
2. When the class is pre-arranged, firstly, all classes are fixedly arranged with the subject to be arranged, then, aiming at the administration subject of each class, the classes are arranged from the first time period of each week to the next according to the sequence of the courses, the class arrangement of the first class is completed, then, from the next class, the classes are arranged from the position of the previous class according to the sequence of the courses, from the top to the bottom, whether the names of teachers with the same subject appear in other classes in the same row is judged, if yes, conflict appears, the classes jump to the last position of the previous class, and the classes are arranged from the bottom to the top; if the conflict still occurs, the course is arranged to the previous vacant position; if all the vacant positions are conflicted, the scheduled class positions are selected for replacement, and the conflict does not occur after replacement, so that the generated initial class schedule can avoid the conflict of physical constraints through the special initialization mode.
2. The genetic algorithm of the invention adopts a new crossing method, carries out pairwise exchange between N (N is a multiple of 2) rows of a certain column under a certain probability, adopts pairwise exchange with small granularity, ensures the convergence stability, introduces a checking mechanism, judges whether conflict violating physical constraint is generated after each crossing, and cancels the crossing operation if the conflict violating physical constraint is generated.
3. The genetic algorithm of the invention adopts a new variation method, if the class schedule is a single-grade class schedule, two lines of the class schedule are exchanged, if the class schedule is a multi-grade class schedule, the multi-grade class schedule is divided into different grades, and two lines of a certain grade are exchanged randomly so as to solve the problem of difficult convergence.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to the structures shown in the drawings without creative efforts.
Fig. 1 is a flowchart of a conventional genetic algorithm.
Fig. 2 is a flowchart of an intelligent course scheduling method for executive class according to embodiment 1 of the present invention.
Fig. 3 is a flowchart of pre-arrangement of courses for fixed departments and administrative courses in sequence according to embodiment 1 of the present invention.
Fig. 4 is a schematic diagram of a class schedule according to embodiment 1 of the present invention.
FIG. 5 is a schematic diagram of a roulette selection method in a conventional genetic algorithm.
Fig. 6 is a diagram illustrating population fitness values of each generation in a conventional genetic algorithm.
FIGS. 7 a-7 b are schematic diagrams of two schedules before crossing in the conventional genetic algorithm, respectively.
FIGS. 8 a-8 b are schematic diagrams of two schedules before crossing in the conventional genetic algorithm, respectively.
FIG. 9a is a table diagram of a genetic algorithm according to example 1 of the present invention before crossover.
FIG. 9b is a schematic diagram of a lesson schedule after crossover in the genetic algorithm of example 1 of the present invention.
FIG. 10a is a table diagram of a genetic algorithm according to example 1 of the present invention before mutation.
FIG. 10b is a schematic diagram of a lesson schedule after mutation in the genetic algorithm in example 1 of the present invention.
Fig. 11 is a block diagram of an intelligent course scheduling system for executive class according to embodiment 2 of the present invention.
Fig. 12 is a block diagram of a pre-lesson arrangement module according to embodiment 2 of the present invention.
Fig. 13 is a block diagram of a computer device according to embodiment 3 of the present invention.
Fig. 14 is a frame diagram of a course arrangement main program module of course arrangement software installed in a computer device according to embodiment 3 of the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer and more complete, the technical solutions in the embodiments of the present invention will be described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are some embodiments of the present invention, but not all embodiments, and all other embodiments obtained by a person of ordinary skill in the art without creative efforts based on the embodiments of the present invention belong to the protection scope of the present invention.
Example 1:
the genetic algorithm is a relatively complete theory and method formed by the research of professor John Holland and colleagues and students of the university of Michigan in the United states, simulates the idea of Darwinian biological evolution theory, and becomes mature as the research of high-performance calculation and modeling direction with system optimization, adaptation and learning. The method is mainly based on an information genetic mechanism and a natural selection principle of excellence and disadvantage in the evolution process, and the population is continuously evolved by using genetic operators such as selection, intersection, mutation and the like from one population, and finally a global optimal solution or an approximately optimal solution is obtained, so that the result can be prevented from falling into local optimal. According to the characteristics of the algorithm, the genetic algorithm is very suitable for course arrangement tables and course arrangement problems.
Genetic algorithms are researched more in recent years, and many meaningful explorations are made in course arrangement, and as a random optimization and search method, the genetic algorithms have two main characteristics:
1) intelligence. After the genetic algorithm determines the coding scheme, the fitness function and the genetic operator, the algorithm organizes and searches by itself by using the information obtained in the evolution process. Individuals with high fitness have a high survival probability, and the adaptive search technology has potential learning ability.
2) Parallelism. Since the genetic algorithm organizes the search in a population-wise manner, it can search multiple regions in the solution space simultaneously and exchange information with each other, although this search only performs calculations proportional to the population size at a time, in essence, it has performed approximately O () significant searches as calculated by Goldberg. This allows genetic algorithms to gain greater gains with fewer computations. Due to the two characteristics of the genetic algorithm, the genetic algorithm is rapidly applied to solve the course scheduling problem of the combinatorial optimization.
The flow chart of the traditional genetic algorithm is shown in fig. 1, the genetic algorithm is complex, the performance speed of the algorithm is reduced when the value range is large and the variables are many, the time consumed during class arrangement is long, and if the limiting conditions are many and complex, an intended solution cannot be obtained.
As shown in fig. 2, the present embodiment provides an intelligent course scheduling method for executive class, which is improved on the basis of the traditional genetic algorithm, and includes the following steps:
s201, reading a teaching plan.
The teaching plan may be read from the database, and the teaching plan includes class, course number, fixed subject, and administrative course subject, and the fixed subject refers to a fixed subject arranged in a fixed time period.
S202, according to the teaching plan, the fixed subject to be arranged and the administrative course subject are subjected to pre-arrangement in sequence.
And S203, generating a plurality of initial class schedules according to the pre-arrangement result.
In this embodiment, the subjects to be scheduled in all classes in the teaching plan are pre-scheduled, and then the subjects of the administrative courses, such as mathematics, Chinese, english, etc., are pre-scheduled for each class, so after the subjects to be scheduled in all classes are pre-scheduled, the subjects of the administrative courses need to be ranked in each class, where Ci is the class and Sj is the subject of the administrative course.
Further, as shown in fig. 3, the step S202 specifically includes:
s2021, calculating the number of courses per week (i.e., the lesson tasks) for each class according to the teaching plan.
And S2022, dividing each week into a plurality of time periods, and taking each time period and each class as the head column and the head row of the school timetable respectively.
As shown in fig. 4, this embodiment divides each week into forty time segments and defines a schedule as one chromosome, where T1-T40 represents forty time segments per week as the top column of the schedule, and C1-CN represents the class as the top row of the schedule.
S2023, the courses are arranged according to the fixed subject to be arranged of all classes.
And S2024, from the first class, the administrative course subjects are arranged from the first time period of each week to the next, and the course arrangement of the first class is completed.
Specifically, according to the above-mentioned course sequence of the administration course subjects of each class, the courses are arranged from the first class to the next from the first time period T1 of each week in the course sequence of the administration course subjects, and the course arrangement of the first class is completed.
And S2025, beginning from the next class, arranging the administrative course subjects from the position of no course arrangement to the next class from top to bottom.
Specifically, according to the course sequence of the administration course subjects of each class, from the next class, the courses are arranged from the position of no course arrangement to the top down according to the course sequence of the administration course subjects.
S2026, judging whether the names of teachers with the same department are presented in other classes in the same row (in the same time period), if yes, conflict occurs, jumping to the last position where courses are not arranged, and arranging courses from bottom to top; if the conflict still occurs, the course is arranged to the previous vacant position; and if all the vacant positions have conflicts, selecting the scheduled positions for replacement, and meeting the requirement that no conflicts occur after replacement.
Since conflicts of physical constraints must be avoided, physical constraints include three types, according to requirements: the teacher can only go to the last course in the same time period (i.e. the same section); students can only go to a previous course in the same time period; only one class can be arranged in one classroom in the same time period, and the latter two conditions are already processed in the time of class division and condition setting, so the two conditions are not considered in the embodiment, and only the first condition is emphasized; because only one course can be arranged in the same time period of the same class in the school timetable, the situation that one teacher has two courses in the same class in the same time period is avoided, and the situation that the same teacher has a class in different classes in the same time period is only avoided; specifically, a certain course of each class is taught by the same manager teacher, and through the dictionary in python, the corresponding manager teacher can be found by the class and the subject, and whether the names of the same manager teacher appear in other classes in the same row or not is judged, so that the situation that the same teacher goes to class in different classes in the same time period can be avoided.
S2027, judging whether all classes are arranged, if so, ending the pre-arrangement course; otherwise, return to step S2025.
With different classes as the first class, through the processing of the steps S2024 to S2027, a plurality of initial schedules can be obtained, and through the special initialization manner of the steps S2024 to S2027, the generated initial schedules can avoid the conflict of physical constraints.
And S204, calculating the population fitness values of a plurality of initial school timetables by adopting a genetic algorithm, and selecting the initial school timetable with the minimum population fitness value as an optimal school timetable.
In the conventional genetic algorithm, the selection operation generally adopts a roulette mode, as shown in fig. 5, the probability of the chromosome being selected is proportional to the fitness, but the selection with small fitness is also possible, for example, if an operator hasFitness is aiNormalized as follows:
Figure BDA0002340422150000081
however, in actual tests, when genetic selection was performed using the roulette algorithm, it was found that the population fitness values of each generation did not differ much, as shown in fig. 6.
Therefore, if the conventional selection operation, i.e., the probability that the proportion of fitness is taken as the chromosome for the selection operation, is used, individuals with better fitness cannot be selected with a high probability, resulting in a tendency of random tropism in the genetic process. The embodiment is improved as follows: for a plurality of chromosomes (a plurality of initial school timetables) of each generation, sorting according to the size of the population fitness value, selecting the chromosome with the minimum population fitness value as the optimal chromosome, namely the optimal school timetable, because the smaller the population fitness value is, the fewer the number of conflicts violating the user requirements in the school timetable is, the optimal school timetable can be reserved in each iteration process, after multiple selection, crossing and variation iterations, the fewer the number of conflicts violating the user requirements in the school timetable is, so that the goal of school timetable convergence is achieved, and finally the user requirements are infinitely close to or even met.
The population fitness value of this embodiment is calculated by using a fitness function, which is as follows:
Figure BDA0002340422150000091
wherein, ω isiThe weight of each fitness function, the size of which is determined by the priority of the user's needs, fiA fitness evaluation function for each user requirement, as follows:
Figure BDA0002340422150000092
wherein N isiTo violate the number of conflicts in the class schedule against user demand i,
Figure BDA0002340422150000093
is a penalty factor.
The user requirements of the embodiment include physical constraints (teacher constraints), solid constraints (hard constraints), forbidden constraints (hard constraints), optimal constraints (soft constraints), dispersion in the week (hard constraints) and concentration in the day (hard constraints), wherein the physical constraints and the solid constraints have been described in the above contents, an evaluation method of the physical constraints is to count whether the same teacher name appears twice or more in the same line (in the same time period) of a class schedule, and an evaluation method of the solid constraints is to judge whether a fixed position is a specified subject, and now the forbidden constraints, the optimal constraints, the dispersion in the week and the concentration in the day are described.
1) Forbidden and optimal steak
The forbidding and the priority are different in the difference that the forbidding is hard constraint and the priority is soft constraint, so that the forbidding and the priority are different in weight, the types of the forbidding and the priority comprise class forbidding and the priority, subject forbidding and the priority, the forbidding and the priority of the teacher is evaluated by whether the forbidding position has the class, the subject and the class scheduling task of the forbidding and the priority of the teacher is empty or has other subjects or the class scheduling task of the teacher.
2) Dispersing in the week
The weekly dispersion means that courses are uniformly arranged in a week, and the weekly dispersion aims to ensure the uniform distribution of teaching tasks, so the evaluation method comprises the following steps: calculating the average value of the day-to-day class tasks of each class, namely dividing the class-to-day tasks by the number of days per week (five days), calculating the absolute value of the difference between the actual class-to-day times of the subjects and the average value, and if the absolute value is more than 1, indicating that the teaching plan is not level.
3) Concentrated in the sky
The intra-day concentration means that the courses of the teachers are arranged in a concentrated manner in a certain time period in the morning or afternoon of a day, and the purpose of the intra-day concentration is to ensure that the courses of the teachers are arranged in the certain time period in the morning or afternoon as concentrated as possible, so the evaluation method comprises the following steps: counting teachers with lessons greater than or equal to 2 in one day, and judging whether the lessons are centrally arranged in a certain time period in the morning or afternoon (generally defined as the morning in the first four sections).
From the above description, equation (2) can be converted into:
F＝w1*f1+w2*f2+w3*f3+w4*f4+w5*f5+w6*f6(4)
wherein:
f1fitness evaluation function representing physical constraints, combined with equation (2), N1The number of conflicts which violate physical constraints is expressed, and the number of classes which the teacher goes to in class in the same time period appears in the class schedule;
f2fitness evaluation function representing solid rank, combined formula (2), N2Representing the number of conflicts violating the fixed ranks, which refers to the number of fixed subjects scheduled in a fixed time period that are not met;
f3fitness evaluation function representing exclusion, combined with equation (2), N3A conflict number representing a ban violation, which is the number of scheduled lessons in a period of time during which the teacher is not scheduling lessons;
f4fitness evaluation function representing a best line, combined with equation (2), N4The conflict number which represents the violation of the priority rank refers to the number of the specified subjects which are not ranked in the specified time period;
f5fitness evaluation function representing dispersion in weeks, combined with formula (2), N5Representing the number of conflicts dispersed within a violation week, meaning that each course needs not to be evenly distributed to each day;
f6shows the fitness evaluation function of the intra-day concentration, in combination with the formula (2), N5The centralized conflict number in the violation day is that the continuous class needs to be kept when the number of courses in one day is greater than or equal to 2, and the centralized conflict number is not arranged in a certain time period in the morning or afternoon;
w1＝2，w2＝1，w3＝1，w4＝1，w5＝1，w6a large weight indicates a high priority level, and processing will be prioritized, 1.
By analogy, if more specific user requirements exist, such as requirements of single and double weeks, classes and the like, only the conflict number needs to be counted in sequence, and thus, if the fitness value is smaller, the user requirements are closer.
And S205, judging whether the population fitness value of the optimal class schedule reaches a preset expected value.
The user can preset a desired value; if the population fitness value of the optimal class schedule reaches the preset expected value, that is, the user requirement is met, the step S206 is entered, and if the population fitness value of the optimal class schedule does not reach the preset expected value, the step S206 is entered until the preset expected value is reached, and then the step S207 is entered.
And S206, outputting the optimal class schedule.
And S207, sequentially crossing and mutating the optimal class schedule, reselecting the optimal class schedule, and returning to the step S205.
The specific description of crossover and variation is as follows:
1) crossing
In biography, the crossing of chromosomes is defined as the partial gene exchange between two parent chromosomes, so as to generate the diversity of biological gene combinations, in course arrangement algorithm, the crossing operation is generally defined as the column-to-column exchange of corresponding columns (same class) between two schedules, the two schedules before crossing are shown in fig. 7 a-7 b, and the two schedules after crossing are shown in fig. 8 a-8 b.
The problem of physical constraint conflict is solved preferentially in the initialization process, but conflict violating the original physical constraint is generated when crossing (column-to-column exchange) is carried out, so that the crossing operation of the embodiment adopts small-granularity pairwise exchange, courses at two positions of a certain column of a schedule are randomly selected for exchange, the convergence stability is ensured, if the exchange granularity is too large, the probability of generating new conflict is increased, and the adaptability value oscillates back and forth and cannot be converged; in addition, the present embodiment introduces a checking mechanism, after each interleaving, the mechanism determines whether a conflict violating the physical constraint occurs, and if so, cancels the interleaving operation this time, and because the exchange between columns easily generates a conflict violating the physical constraint, the interleaving operation is difficult to perform.
2) Variation of
The mutation is defined in biology as the structural change of chromosome itself, and in this embodiment, the genetic manipulation of the mutation is defined as the exchange of two lines (two time periods) of the schedule itself, and the schedule before the mutation is shown in FIG. 9a, and the schedule after the mutation is shown in FIG. 9 b.
The above is the variation operation of the class schedule aiming at a single grade, however, because there is a requirement of arranging classes simultaneously for multiple grades in the requirement, and because the class number is increased when the classes are arranged for multiple grades, and there is a situation that a teacher teaches multiple grades, the class schedule of a single grade cannot be simply recursively called, and when genetic variation is performed, the alternation of two lines of the whole class schedule can cause overlarge fluctuation and is difficult to converge.
Therefore, for the class schedules of multiple grades, the embodiment is improved as follows: the class schedules of a plurality of grades are divided into different grades, two lines of a certain grade are exchanged at random, because a manager teacher possibly has the condition that the teacher goes to class in the plurality of grades in the same time period, if the two lines of the certain grade are exchanged, conflicts violating physical constraints can possibly be generated, therefore, the embodiment also introduces an inspection mechanism, after the two lines of the certain grade are exchanged, whether the conflicts violating the physical constraints are generated is judged, and if yes, the mutation operation is cancelled.
After crossing and mutation, reselecting the best class schedule by using the method of step S203, and then returning to step S204; and if the population fitness value of the optimal class schedule still does not reach the preset expected value after twenty-thousand iterations, outputting the optimal class schedule.
Those skilled in the art will appreciate that all or part of the steps in the method for implementing the above embodiments may be implemented by a program to instruct associated hardware, and the corresponding program may be stored in a computer-readable storage medium.
It should be noted that although the method operations of the above-described embodiments are depicted in the drawings in a particular order, this does not require or imply that these operations must be performed in this particular order, or that all of the illustrated operations must be performed, to achieve desirable results. Rather, the depicted steps may change the order of execution. Additionally or alternatively, certain steps may be omitted, multiple steps combined into one step execution, and/or one step broken down into multiple step executions.
Example 2:
as shown in fig. 11, the present embodiment provides an intelligent class scheduling system for executive shift, which includes a reading module 1101, a pre-scheduling module 1102, a generating module 1103, a selecting module 1104, a determining module 1105, an outputting module 1106, and a cross mutation module 1107, where the specific functions of the modules are as follows:
the reading module 1101 is configured to read a teaching plan.
The pre-course arrangement module 1102 is configured to perform pre-course arrangement on fixed subjects to be arranged and administrative course subjects in sequence according to the teaching plan.
The generating module 1103 is configured to generate a plurality of initial lesson schedules according to the pre-arrangement lesson result; the initial class schedule is arranged in each time period, and the initial class schedule is arranged in each class.
The selection module 1104 is configured to calculate population fitness values of a plurality of initial school timetables by using a genetic algorithm, and select an initial school timetable with the smallest population fitness value as an optimal school timetable.
The determining module 1105 is configured to determine whether the population fitness value of the best class schedule reaches a preset expected value.
The output module 1106 is configured to output the optimal class schedule if the population fitness value of the optimal class schedule reaches a preset expected value.
And the cross variation module 1107 is configured to, if the population fitness value of the optimal class schedule does not reach the preset expected value, sequentially cross and vary the optimal class schedule, reselect the optimal class schedule, return to the judgment of whether the population fitness value of the optimal class schedule reaches the preset expected value, and perform subsequent operations.
Further, the pre-lesson-arrangement module 1102, as shown in fig. 12, specifically includes:
a calculating unit 11021, configured to calculate the number of courses per week for each class according to the teaching plan.
A dividing unit 11022, configured to divide each week into a plurality of time periods, and take each time period and each class as a head column and a head row of the schedule, respectively.
And the first course arrangement unit 11023 is used for arranging courses of the subjects to be arranged fixedly in all classes.
And a second course arrangement unit 11024, configured to, starting from the first class, arrange the courses of the administration courses from the first time period of each week to the next, and complete course arrangement of the first class.
And a third course arrangement unit 11025 configured to arrange the courses from top to bottom starting from the next class from the position where the administrative subjects are not arranged.
A first determining unit 11026, configured to determine whether names of teachers with the same department have appeared in other classes in the same row, if yes, a conflict appears, and then jump to the last position where the class is not arranged, and arrange the class from bottom to top; if the conflict still occurs, the course is arranged to the previous vacant position; and if all the vacant positions have conflicts, selecting the scheduled positions for replacement, and meeting the requirement that no conflicts occur after replacement.
A second determination unit 11027, configured to determine whether all classes are scheduled, and if so, end the pre-scheduling; otherwise, returning to the next class, and arranging the administrative course subjects from the position of the non-arranged course from top to bottom and executing the subsequent operation.
The specific implementation of each module in this embodiment may refer to embodiment 1, which is not described herein any more; it should be noted that the system provided in this embodiment is only illustrated by the division of the functional modules, and in practical applications, the functions may be distributed by different functional modules according to needs, that is, the internal structure is divided into different functional modules to complete all or part of the functions described above.
Example 3:
the present embodiment provides a computer device, which is a computer, as shown in fig. 13, and is a processor 1302, a memory, an input device 1303, a display 1304 and a network interface 1305 connected by a system bus 1301, where the processor is used to provide computing and control capabilities, the memory includes a nonvolatile storage medium 1306 and an internal memory 1307, the nonvolatile storage medium 1306 stores an operating system, computer programs and a database, the internal memory 1307 provides an environment for the operation of the operating system and the computer programs in the nonvolatile storage medium, and when the processor 1302 executes the computer programs stored in the memory, the intelligent class scheduling method for executive class in embodiment 1 is implemented as follows:
reading a teaching plan;
according to the teaching plan, pre-arrangement courses are sequentially carried out on fixed subjects to be arranged and administrative course subjects;
generating a plurality of initial class schedules according to the pre-arrangement result; the initial class schedule comprises a first time slot, a second time slot, a third time slot and a fourth time slot, wherein the first time slot is a time slot, and the first time slot is a time slot of each class;
calculating the population fitness values of a plurality of initial school timetables by adopting a genetic algorithm, and selecting the initial school timetable with the minimum population fitness value as an optimal school timetable;
judging whether the population fitness value of the optimal class schedule reaches a preset expected value or not;
if the population fitness value of the optimal class schedule reaches a preset expected value, outputting the optimal class schedule;
and if the population fitness value of the optimal class schedule does not reach the preset expected value, sequentially crossing and mutating the optimal class schedule, reselecting the optimal class schedule, returning to judge whether the population fitness value of the optimal class schedule reaches the preset expected value or not, and executing subsequent operation.
Further, according to the teaching plan, the fixed subject to be arranged and the administrative course subject are arranged in advance in sequence, and the method specifically comprises the following steps:
calculating the number of courses per week of each class according to the teaching plan;
dividing each week into a plurality of time periods, and respectively taking each time period and each class as a head column and a head row of a school timetable;
the subject to be ranked is fixed in all classes for course ranking;
from the first class, the administrative course subjects are arranged from the first time slot of each week to the next, and the first class arrangement is completed;
starting from the next class, and arranging the administrative course subjects from the position of no course arrangement from top to bottom;
judging whether the names of teachers with the same department appear in other classes in the same row, if so, jumping to the final position where the courses are not arranged, and arranging the courses from bottom to top; if the conflict still occurs, the course is arranged to the previous vacant position; if all the vacant positions have conflicts, selecting the scheduled class positions for replacement, and meeting the requirement that no conflicts occur after replacement;
judging whether all classes are arranged, if so, finishing the pre-arrangement of the classes; otherwise, returning to the next class, and arranging the administrative course subjects from the position of the non-arranged course from top to bottom and executing the subsequent operation.
Further, the crossing of the optimal class schedules specifically comprises:
randomly selecting courses at two positions in a certain column in the optimal class schedule for exchange;
and after the courses of the two positions are exchanged, judging whether a conflict of violating physical constraints is generated, and if so, canceling the cross operation.
Further, the method for changing the crossed optimal class schedules specifically comprises the following steps:
if the crossed optimal class schedule is the class schedule of a single grade, exchanging two lines of the class schedule of the single grade;
if the crossed optimal schedules are schedules in multiple grades, dividing the schedules in the multiple grades into different grades, and randomly interchanging two lines in a certain grade;
and after the two rows of a certain grade are exchanged, judging whether conflict of violating physical constraints occurs, and if so, cancelling the mutation operation.
The computer device of the present embodiment may be installed with a course arrangement software capable of implementing the above-mentioned intelligent course arrangement method for executive class, wherein a main course arrangement program module is shown in fig. 14 and includes an initialization unit, an evaluation unit and a genetic unit.
The initialization unit is used for constructing an initial population, namely an initial class schedule (an initial class schedule), and comprises administrative class initialization, and specifically comprises the following steps: reading a teaching plan; according to the teaching plan, pre-arrangement courses are sequentially carried out on fixed subjects to be arranged and administrative course subjects; and generating a plurality of initial class schedules according to the pre-arrangement result.
The evaluation unit is used for evaluating the advantages and disadvantages of the generated school timetable, including physical constraints, hard constraints and soft constraints, which have different contribution degrees to the evaluation, and the evaluation of various constraints is mainly completed by using the formula (3) of the embodiment 1.
The genetic unit is used for generating a new population, namely a new offspring class table, and comprises selection operation, cross operation and mutation operation, and specifically comprises the following steps: selecting an initial class schedule with the minimum population fitness value as an optimal class schedule; judging whether the population fitness value of the optimal class schedule reaches a preset expected value or not; if the population fitness value of the optimal class schedule reaches a preset expected value, outputting the optimal class schedule; and if the population fitness value of the optimal class schedule does not reach the preset expected value, sequentially crossing and mutating the optimal class schedule, reselecting the optimal class schedule, returning to judge whether the population fitness value of the optimal class schedule reaches the preset expected value or not, and executing subsequent operation.
Example 4:
the present embodiment provides a storage medium, which is a computer-readable storage medium, and stores a computer program, and when the computer program is executed by a processor, the method for intelligently scheduling a class for an administrative shift according to embodiment 1 above is implemented as follows:
reading a teaching plan;
according to the teaching plan, pre-arrangement courses are sequentially carried out on fixed subjects to be arranged and administrative course subjects;
generating a plurality of initial class schedules according to the pre-arrangement result; the initial class schedule comprises a first time slot, a second time slot, a third time slot and a fourth time slot, wherein the first time slot is a time slot, and the first time slot is a time slot of each class;
calculating the population fitness values of a plurality of initial school timetables by adopting a genetic algorithm, and selecting the initial school timetable with the minimum population fitness value as an optimal school timetable;
judging whether the population fitness value of the optimal class schedule reaches a preset expected value or not;
if the population fitness value of the optimal class schedule reaches a preset expected value, outputting the optimal class schedule;
and if the population fitness value of the optimal class schedule does not reach the preset expected value, sequentially crossing and mutating the optimal class schedule, reselecting the optimal class schedule, returning to judge whether the population fitness value of the optimal class schedule reaches the preset expected value or not, and executing subsequent operation.
Further, according to the teaching plan, the fixed subject to be arranged and the administrative course subject are arranged in advance in sequence, and the method specifically comprises the following steps:
calculating the number of courses per week of each class according to the teaching plan;
dividing each week into a plurality of time periods, and respectively taking each time period and each class as a head column and a head row of a school timetable;
the subject to be ranked is fixed in all classes for course ranking;
from the first class, the administrative course subjects are arranged from the first time slot of each week to the next, and the first class arrangement is completed;
starting from the next class, and arranging the administrative course subjects from the position of no course arrangement from top to bottom;
judging whether the names of teachers with the same department appear in other classes in the same row, if so, jumping to the final position where the courses are not arranged, and arranging the courses from bottom to top; if the conflict still occurs, the course is arranged to the previous vacant position; if all the vacant positions have conflicts, selecting the scheduled class positions for replacement, and meeting the requirement that no conflicts occur after replacement;
judging whether all classes are arranged, if so, finishing the pre-arrangement of the classes; otherwise, returning to the next class, and arranging the administrative course subjects from the position of the non-arranged course from top to bottom and executing the subsequent operation.
Further, the crossing of the optimal class schedules specifically comprises:
randomly selecting courses at two positions in a certain column in the optimal class schedule for exchange;
and after the courses of the two positions are exchanged, judging whether a conflict of violating physical constraints is generated, and if so, canceling the cross operation.
Further, the method for changing the crossed optimal class schedules specifically comprises the following steps:
if the crossed optimal class schedule is the class schedule of a single grade, exchanging two lines of the class schedule of the single grade;
if the crossed optimal schedules are schedules in multiple grades, dividing the schedules in the multiple grades into different grades, and randomly interchanging two lines in a certain grade;
and after the two rows of a certain grade are exchanged, judging whether conflict of violating physical constraints occurs, and if so, cancelling the mutation operation.
The storage medium described in this embodiment may be a magnetic disk, an optical disk, a computer Memory, a Random Access Memory (RAM), a usb disk, a removable hard disk, or other media.
In summary, according to the teaching plan, the invention performs pre-arrangement on fixed subjects to be arranged and administrative classes in sequence, generates a plurality of initial school timetables according to the pre-arrangement result, calculates the population fitness value of the plurality of initial school timetables by adopting a genetic algorithm, selects the initial school timetable with the smallest population fitness value as the optimal school timetable, outputs the optimal school timetable if the population fitness value of the optimal school timetable reaches the preset expectation value, and performs intersection and variation on the optimal school timetable in sequence if the population fitness value of the optimal school timetable does not reach the preset expectation value, and then reselects the optimal school timetable until the population fitness value reaches the preset expectation value, so that the genetic process is performed towards the predicted direction, and convergence can be faster, and the actual test shows that the arranged school timetable can meet the actual requirements of the administrative classes of primary and middle schools.
The above description is only for the preferred embodiments of the present invention, but the protection scope of the present invention is not limited thereto, and any person skilled in the art can substitute or change the technical solution and the inventive concept of the present invention within the scope of the present invention.

Claims (10)

1.一种行政班智能排课方法，其特征在于，所述方法包括：1. an administrative class intelligent class arrangement method, is characterized in that, described method comprises: 读取教学计划；read the lesson plan; 根据教学计划，将固定要排的科目、行政课科目依次进行预排课；According to the teaching plan, pre-arrange the fixed subjects and administrative subjects in turn; 根据预排课结果，生成多张初始课表；其中，所述初始课表的首列为各个时间段，初始课表的首行为各个班级；According to the pre-arrangement result, a plurality of initial class schedules are generated; wherein, the first column of the initial class schedule is each time period, and the first column of the initial class schedule is each class; 采用遗传算法，计算多张初始课表的种群适应度值，选择种群适应度值最小的初始课表作为最佳课表；Using genetic algorithm to calculate the population fitness value of multiple initial class schedules, select the initial class schedule with the smallest population fitness value as the best class schedule; 判断最佳课表的种群适应度值是否达到预设期望值；Determine whether the population fitness value of the best class schedule reaches the preset expected value; 若最佳课表的种群适应度值达到预设期望值，则输出该最佳课表；If the population fitness value of the best class schedule reaches the preset expected value, output the best class schedule; 若最佳课表的种群适应度值未达到预设期望值，则将最佳课表依次进行交叉、变异，重新选择最佳课表，返回判断最佳课表的种群适应度值是否达到预设期望值，并执行后续操作。If the population fitness value of the best class schedule does not reach the preset expected value, the best class schedule will be crossed and mutated in turn, and the best class schedule will be re-selected, and return to determine whether the population fitness value of the best class schedule has reached the preset expected value, and execute Follow-up action. 2.根据权利要求1所述的行政班智能排课方法，其特征在于，所述根据教学计划，将固定要排的科目、行政课科目依次进行预排课，具体包括：2. The intelligent class scheduling method for administrative classes according to claim 1, characterized in that, according to the teaching plan, the subjects to be scheduled and the subjects of administrative classes are scheduled to be scheduled in turn, specifically including: 根据教学计划，计算每个班级的每周课程数；Calculate the number of weekly lessons for each class according to the teaching plan; 将每周划分为多个时间段，并将各个时间段和各个班级分别作为课表的首列和首行；Divide the week into multiple time periods, and use each time period and each class as the first column and first row of the class schedule; 将所有班级固定要排的科目进行排课；Arrange the subjects that are fixed to be arranged in all classes; 从第一个班级开始，将行政课科目从每周的第一个时间段往下排课，完成第一个班级排课；Starting from the first class, arrange the administrative subjects from the first time period of the week down, and complete the first class arrangement; 从下一个班级开始，将行政课科目从未排课位置开始，从上往下排课；Starting from the next class, the administrative subjects will start from the unscheduled position, and the classes will be arranged from the top to the bottom; 判断同一行中其他班级是否已经出现相同科任教师的名字，若是，即出现冲突，则跳至未排课的最后位置，从下往上排课；若仍然出现冲突，则往上一个空位排课；若所有空位都出现冲突，则选择已排课位置进行替换，且需满足替换后不出现冲突；Judge whether the name of the teacher of the same subject has already appeared in other classes in the same row. If there is a conflict, skip to the last position where the class is not scheduled, and arrange the class from the bottom to the top; if there is still a conflict, go to the upper vacancy class; if all the vacancies conflict, select the class that has been scheduled for replacement, and it must be satisfied that there is no conflict after the replacement; 判断是否排完所有班级，若是，则结束预排课；否则，返回从下一个班级开始，将行政课科目从未排课位置开始，从上往下排课，并执行后续操作。It is judged whether all the classes have been arranged, and if so, end the pre-arranged classes; otherwise, return to start from the next class, arrange the administrative subjects from the unscheduled position, arrange the classes from the top to the bottom, and perform the follow-up operations. 3.根据权利要求1所述的行政班智能排课方法，其特征在于，所述种群适应度值采用适应度函数计算，所述适应度函数如下式：3. The intelligent class scheduling method for administrative classes according to claim 1, wherein the population fitness value is calculated by a fitness function, and the fitness function is as follows:
Figure FDA0002340422140000021
Figure FDA0002340422140000021
 其中，ωi为每个适应度函数的权重，其大小由用户需求的优先级决定，fi为每个用户需求的适应度评价函数，如下式：Among them, ω i is the weight of each fitness function, and its size is determined by the priority of user requirements, and f i is the fitness evaluation function of each user requirement, as follows:
Figure FDA0002340422140000022
Figure FDA0002340422140000022
 其中，Ni为在课表中违反用户需求i的冲突数量，
Figure FDA0002340422140000023
为惩罚因子。Among them, Ni is the number of conflicts that violate the user's requirement i in the curriculum,
Figure FDA0002340422140000023
is the penalty factor. 4.根据权利要求3所述的行政班智能排课方法，其特征在于，所述用户需求包括物理约束、固排、禁排、优排、周内分散和天内集中；4. The intelligent class scheduling method for administrative classes according to claim 3, wherein the user requirements include physical constraints, fixed row, forbidden row, optimal row, scattered within a week and concentrated within a day; 所述物理约束是指：教师在同一个时间段只能上一门课程；The physical constraints refer to: teachers can only take one course in the same time period; 所述固排是指：在固定时间段安排固定科目；The fixed arrangement refers to: arranging fixed subjects in a fixed time period; 所述禁排是指：禁止在不该排课的时间段安排教师上课；The prohibition of arranging means: prohibiting teachers from arranging classes during the time period when classes should not be scheduled; 所述优排是指：在指定的时间段安排指定科目；The preferential arrangement refers to: arranging designated subjects in a designated time period; 所述周内分散是指：在一周内均匀安排课程；The said intra-week dispersion refers to: evenly arranging courses within a week; 所述天内集中是指：将教师的课程集中安排在一天的上午或下午的某个时间段。The intraday concentration refers to: arranging the teacher's courses in a certain time period in the morning or afternoon of the day. 5.根据权利要求1-4任一项所述的行政班智能排课方法，其特征在于，将最佳课表进行交叉，具体包括：5. The intelligent class scheduling method for administrative classes according to any one of claims 1-4, wherein the best class schedule is crossed, specifically comprising: 随机选取最佳课表中某一列的两个位置的课程进行交换；Randomly select courses in two positions in a column in the best course schedule to exchange; 当两个位置的课程交换后，判断是否产生违反物理约束的冲突，若是，则取消本次交叉操作。When the courses of the two locations are exchanged, it is judged whether there is a conflict that violates the physical constraints, and if so, the crossover operation is canceled. 6.根据权利要求1-4任一项所述的行政班智能排课方法，其特征在于，将交叉后的最佳课表进行变异，具体包括：6. The intelligent class scheduling method for administrative classes according to any one of claims 1-4, characterized in that, mutating the best class schedule after the crossover, specifically comprising: 若交叉后的最佳课表为单个年级的课表，则将单个年级的课表的两行进行互换；If the best timetable after crossover is the timetable of a single grade, then exchange the two lines of the timetable of a single grade; 若交叉后的最佳课表为多个年级的课表，则将多个年级的课表分为不同年级，随机对某个年级的两行进行互换；If the best timetable after crossover is the timetable of multiple grades, divide the timetables of multiple grades into different grades, and randomly exchange two rows of a grade; 当某个年级的两行进行互换后，判断是否产生违反物理约束的冲突，若是，则取消本次变异操作。When the two rows of a certain grade are exchanged, it is judged whether there is a conflict that violates the physical constraints, and if so, the mutation operation is canceled. 7.一种行政班智能排课系统，其特征在于，所述系统包括：7. An intelligent class scheduling system for administrative classes, characterized in that the system comprises: 读取模块，用于读取教学计划；Reading module, used to read the teaching plan; 预排课模块，用于根据教学计划，将固定要排的科目、行政课科目依次进行预排课；The pre-arrangement module is used to pre-arrange the fixed subjects and administrative subjects in sequence according to the teaching plan; 生成模块，用于根据预排课结果，生成多张初始课表；其中，所述初始课表的首列为各个时间段，初始课表的首行为各个班级；The generation module is used to generate a plurality of initial class schedules according to the results of pre-arranging classes; wherein, the first row of the initial class schedule is each time period, and the first row of the initial class schedule is each class; 选择模块，用于采用遗传算法，计算多张初始课表的种群适应度值，选择种群适应度值最小的初始课表作为最佳课表；The selection module is used to calculate the population fitness value of multiple initial class schedules by using genetic algorithm, and select the initial class schedule with the smallest population fitness value as the best class schedule; 判断模块，用于判断最佳课表的种群适应度值是否达到预设期望值；The judgment module is used to judge whether the population fitness value of the best class schedule reaches the preset expected value; 输出模块，用于若最佳课表的种群适应度值达到预设期望值，则输出该最佳课表；The output module is used for outputting the optimal class schedule if the population fitness value of the best class schedule reaches the preset expected value; 交叉变异模块，用于若最佳课表的种群适应度值未达到预设期望值，则将最佳课表依次进行交叉、变异，重新选择最佳课表，返回判断最佳课表的种群适应度值是否达到预设期望值，并执行后续操作。Crossover mutation module, if the population fitness value of the best curriculum does not reach the preset expected value, the best curriculum will be crossed and mutated in turn, and the best curriculum will be reselected, and return to determine whether the population fitness value of the best curriculum has reached the desired value. Preset expected values, and perform subsequent actions. 8.根据权利要求7所述的行政班智能排课系统，其特征在于，所述预排课模块，具体包括：8. The intelligent class scheduling system for administrative classes according to claim 7, wherein the pre-arranging class module specifically comprises: 计算单元，用于根据教学计划，计算每个班级的每周课程数；The calculation unit is used to calculate the number of weekly lessons for each class according to the teaching plan; 划分单元，用于将每周划分为多个时间段，并将各个时间段和各个班级分别作为课表的首列和首行；The division unit is used to divide the week into multiple time periods, and use each time period and each class as the first column and first row of the class schedule; 第一排课单元，用于将所有班级固定要排的科目进行排课；The first row of lesson units is used to arrange the subjects that are fixed to be arranged in all classes; 第二排课单元，用于从第一个班级开始，将行政课科目从每周的第一个时间段往下排课，完成第一个班级排课；The second row of lesson units is used to start from the first class, arrange the administrative subjects from the first time period of the week down, and complete the first class schedule; 第三排课单元，用于从下一个班级开始，将行政课科目从未排课位置开始，从上往下排课；The third row of lesson units is used to start from the next class, and arrange the administrative subjects from the unscheduled position, and arrange the lessons from the top to the bottom; 第一判断单元，用于判断同一行中其他班级是否已经出现相同科任教师的名字，若是，即出现冲突，则跳至未排课的最后位置，从下往上排课；若仍然出现冲突，则往上一个空位排课；若所有空位都出现冲突，则选择已排课位置进行替换，且需满足替换后不出现冲突；The first judgment unit is used to judge whether the name of the teacher of the same subject has appeared in other classes in the same row. If there is a conflict, it will jump to the last position where the class has not been scheduled, and the class will be scheduled from bottom to top; if there is still a conflict , then go to the next vacancy to schedule a class; if all vacancies conflict, select the scheduled class to replace, and it must be satisfied that there is no conflict after the replacement; 第二判断单元，用于判断是否排完所有班级，若是，则结束预排课；否则，返回从下一个班级开始，将行政课科目从未排课位置开始，从上往下排课，并执行后续操作。The second judging unit is used to judge whether all the classes have been arranged, and if so, end the pre-arranged classes; otherwise, return to the next class, start from the unscheduled position, and arrange the classes from the top to the bottom. Perform subsequent operations. 9.一种计算机设备，包括处理器以及用于存储处理器可执行程序的存储器，其特征在于，所述处理器执行存储器存储的程序时，实现权利要求1-6任一项所述的行政班智能排课方法。9. A computer device comprising a processor and a memory for storing a program executable by the processor, characterized in that, when the processor executes the program stored in the memory, the administrative procedure described in any one of claims 1-6 is realized. Smart class scheduling method. 10.一种存储介质，存储有程序，其特征在于，所述程序被处理器执行时，实现权利要求1-6任一项所述的行政班智能排课方法。10 . A storage medium storing a program, wherein when the program is executed by a processor, the method for intelligently scheduling administrative classes according to any one of claims 1 to 6 is implemented. 11 .
CN201911374006.4A 2019-12-27 2019-12-27 Intelligent course scheduling method and system for administrative classes, computer equipment and storage medium Active CN111161112B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201911374006.4A CN111161112B (en) 2019-12-27 2019-12-27 Intelligent course scheduling method and system for administrative classes, computer equipment and storage medium

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201911374006.4A CN111161112B (en) 2019-12-27 2019-12-27 Intelligent course scheduling method and system for administrative classes, computer equipment and storage medium

Publications (2)

Publication Number Publication Date
CN111161112A true CN111161112A (en) 2020-05-15
CN111161112B CN111161112B (en) 2023-04-18

Family

ID=70558486

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911374006.4A Active CN111161112B (en) 2019-12-27 2019-12-27 Intelligent course scheduling method and system for administrative classes, computer equipment and storage medium

Country Status (1)

Country Link
CN (1) CN111161112B (en)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112256188A (en) * 2020-10-21 2021-01-22 杭州布谷蓝途科技有限公司 Course arrangement scheme generation method and device, corresponding computer equipment, storage medium, course arrangement system and course arrangement method
CN118193990A (en) * 2024-05-16 2024-06-14 安徽中医药大学第一附属医院 Automatic review method and system for electronic medical records based on multi-population analysis
CN118898383A (en) * 2024-10-09 2024-11-05 浙江海亮科技有限公司 A method of scheduling classes

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5319781A (en) * 1991-05-03 1994-06-07 Bolt Beranek And Newman Inc. Generation of schedules using a genetic procedure
EP1345167A1 (en) * 2002-03-12 2003-09-17 BRITISH TELECOMMUNICATIONS public limited company Method of combinatorial multimodal optimisation
US20040030420A1 (en) * 2002-07-30 2004-02-12 Ulyanov Sergei V. System and method for nonlinear dynamic control based on soft computing with discrete constraints
CN105550751A (en) * 2015-12-15 2016-05-04 重庆大学 Steelmaking-continuous casting scheduling method utilizing priority policy hybrid genetic algorithm
CN105809315A (en) * 2014-12-31 2016-07-27 北京大唐高鸿软件技术有限公司 Method for automatically arranging electronic curriculum schedules of middle and primary schools
CN109165799A (en) * 2018-10-24 2019-01-08 大连明易科技有限公司 Class-walking teaching scheduling system based on genetic algorithm
CN109255512A (en) * 2018-07-12 2019-01-22 浙江工业大学 A kind of Course Arrangement in University method based on Monte Carlo genetic algorithm
CN109961226A (en) * 2019-03-22 2019-07-02 深圳市倍思教育科技有限公司 Cource arrangement method, device, computer equipment and storage medium

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5319781A (en) * 1991-05-03 1994-06-07 Bolt Beranek And Newman Inc. Generation of schedules using a genetic procedure
EP1345167A1 (en) * 2002-03-12 2003-09-17 BRITISH TELECOMMUNICATIONS public limited company Method of combinatorial multimodal optimisation
US20040030420A1 (en) * 2002-07-30 2004-02-12 Ulyanov Sergei V. System and method for nonlinear dynamic control based on soft computing with discrete constraints
CN105809315A (en) * 2014-12-31 2016-07-27 北京大唐高鸿软件技术有限公司 Method for automatically arranging electronic curriculum schedules of middle and primary schools
CN105550751A (en) * 2015-12-15 2016-05-04 重庆大学 Steelmaking-continuous casting scheduling method utilizing priority policy hybrid genetic algorithm
CN109255512A (en) * 2018-07-12 2019-01-22 浙江工业大学 A kind of Course Arrangement in University method based on Monte Carlo genetic algorithm
CN109165799A (en) * 2018-10-24 2019-01-08 大连明易科技有限公司 Class-walking teaching scheduling system based on genetic algorithm
CN109961226A (en) * 2019-03-22 2019-07-02 深圳市倍思教育科技有限公司 Cource arrangement method, device, computer equipment and storage medium

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
张春红等: "现代高校排课系统的设计与分析", 《科技信息(学术研究)》 *
李阳等: "基于改进遗传算法的高校排课优化问题研究", 《电子科技》 *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112256188A (en) * 2020-10-21 2021-01-22 杭州布谷蓝途科技有限公司 Course arrangement scheme generation method and device, corresponding computer equipment, storage medium, course arrangement system and course arrangement method
CN118193990A (en) * 2024-05-16 2024-06-14 安徽中医药大学第一附属医院 Automatic review method and system for electronic medical records based on multi-population analysis
CN118898383A (en) * 2024-10-09 2024-11-05 浙江海亮科技有限公司 A method of scheduling classes

Also Published As

Publication number Publication date
CN111161112B (en) 2023-04-18

Similar Documents

Publication Publication Date Title
CN111178751B (en) Intelligent course scheduling method, system, computer equipment and storage media for the new college entrance examination
Fischer et al. The process of solving complex problems
Pillay A survey of school timetabling research
Bettinelli et al. An overview of curriculum-based course timetabling
CN111161112B (en) Intelligent course scheduling method and system for administrative classes, computer equipment and storage medium
Wen-jing Improved Adaptive Genetic Algorithm for Course Scheduling in Colleges and Universities.
Ponomareva et al. Instrumental implementation of the educational process model to improve the rating of the universities.
CN111539581A (en) Intelligent class scheduling method and system for different shifts
Echegaray-Calderon et al. Optimal selection of factors using Genetic Algorithms and Neural Networks for the prediction of students' academic performance
Hosny et al. A mutation-based genetic algorithm for room and proctor assignment in examination scheduling
Doulaty et al. Timetabling: A state-of-the-art evolutionary approach
Kuchkarova et al. Quality management of engineering graphics teaching
Aru et al. Effects of School-Related Factors and Early Learning Experiences on Mathematics Achievement" A Multilevel Analysis to Analyse the TIMSS Data".
OROZOVA et al. Generalized net model for dynamic decision making and prognoses
Long A genetic algorithm based method for timetabling problems using linguistics of hedge algebra in constraints
Smirnov et al. formal evolutionary modeling for political scientists
Pambudi et al. Genetic algorithm for teaching distribution based on lecturers’ expertise
Fedorchenko et al. Development of a modified genetic method for automatic university scheduling.
Glibovets et al. Genetic algorithms used to solve scheduling problems
Stroganov et al. The Optimization Methodology of the Digital Model of the Educational Program Based on Learning-Forgetting Functions
Ivohin et al. On the influence of fuzzy perception of the time passage speed on the solutions of optimization planning problems
Odim et al. On the Fitness Measure of Genetic Algorithm for Generating Institutional Lecture Timetable
Xiao et al. Efficiently solving high school timetable scheduling problems with various neighborhood operators
Nuntasen et al. A novel approach of genetic algorithm for solving university timetabling problems: a case study of Thai universities
Qin et al. An intelligent course scheduling model based on genetic algorithm

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CP03 Change of name, title or address

Address after: 510700 room 106, room 406, No. 1, Yichuang street, Zhongxin Guangzhou Knowledge City, Huangpu District, Guangzhou City, Guangdong Province

Patentee after: Guangdong Yijiaotong Technology Co.,Ltd.

Country or region after: China

Address before: Room 1001, 10th Floor, No. 89 Zhongshan Avenue, Tianhe District, Guangzhou City, Guangdong Province, 510630

Patentee before: GUANGDONG ETONEDU CO.,LTD.

Country or region before: China

CP03 Change of name, title or address