Organizing problems and defining requirements
Overview
In this article, we explain how to organize information of the problem that you want to solve, which will
be done in the
requirements definition stage, using the "school class timetable" as a motif.
By organizing the relevant information, you can begin to understand the issue's characteristics and the
fact that it is
a combinatorial optimization.
Let's go through how to clarify the problem to input the assignment into the computer as an optimization
problem.
Topic: Automatically Create "School Class Timetable"
When teachers create timetables in schools, some use specialized software, but most are working on their
hands to ensure
that they can take into account the conditions without conflicts.
For the sake of setting up an example of a combinatorial optimization problem that is a somewhat complex
yet
easy-to-think-about, let's assume we are creating a class timetable for a subject-teacher system in a
fictitious high
school.
Since this is a "subject teacher system," a subject teacher must be assigned to a particular time block
for a class and
there must be no other conflicts.
Given these conditions and constraints, we can formulate the problem as a combinatorial optimization to
determine each
teacher to be assigned ($+1$) or not ($-1$) to each time block for a week.
Attention!
Timetabling is a combinatorial optimization problem that determines the best combination of a teacher for
a subject
(e.g., Mr. John's math) and a time block (e.g., 5th Grade, Class 2, the 2nd block on Tuesday). We will set
($+1$) if the
teacher is allocated to the time block or ($-1$) if not.
Next, think about which conditions are necessary for solving this problem.
STEP1. verbalize the problem (requirements definition)
The requirement definition is to verbalize a problem in the real world. We want a computer to process the
solution of
the timetable problem, but in terms of the use of IT, the computer will not work with vague instructions.
To accurately
convey what we want, we start by carefully verbalizing the prerequisite information for creating the
timetable, which is
a real problem. We will organize the given information as follows.
Subjects and teachers
There are nine subjects: Japanese, English, Mathematics, Science, Social Studies, Physical Education,
Art, Music, and
Life. All of these are conducted by specialized teachers. There are eight teachers each for Japanese,
English, and
mathematics, and four each for the other subjects.
Classes
- There are two classes each for six grades, for a total of 12 classes.
- Note that the number of subjects is the same from grade to grade and class to class, and subject
teachers can be
assigned to any grade and class.
Working duty
- Each teacher must work five blocks or more per week.
Timetable
- The maximum number of classes conducted in one day is six.
- There are five days a week, from Monday to Friday.
Constraints
- Each timetable must allocate five blocks each for Japanese, English, and mathematics, and two blocks
each for the other
subjects.
- No more than two consecutive blocks of the same subject are in the same class.
- To avoid overwork for teachers, the same teacher must not work for more than five consecutive blocks.
Thus, by verbalizing the issue, the rules become clear. When the rules are clarified in words, it is
easier to respond
to changes in faculty or minor additions or changes in the rules.
STEP 2. write down and define what you want the computer to handle
(1) Let the teachers be group A, and assign a code number starting from "A" to each
subject teacher.
- Japanese A01~A08, English A09~A18, Mathematics A19~A27,
- Science A28~A31, Social Studies A32~A39, Physical Education A40~A44, Art A45~A49, Music A50~A54, Life
A55~A59
(2) Let the time blocks be group B, and assign a code number starting from "B" to
each blocks.
- Class number 01-12
- Number the frames Monday 1st period = 01, 2nd period = 02, Tuesday 1st period = 07, Friday 6th period
= 30
- Class 1, Monday 1st period = B0101, 2nd period = B0102, Tuesday 1st period = B0107, Friday 6th period
= B0130
(3) Assign each element of group A (from A01 to A40) to any element of group B
(B0101 to B1230)
(4) This process must follow the constraints below;
- A teacher cannot be allocated to multiple blocks held at the same time.
- In one timetable (one class), any five blocks must have teacher numbers selected from A01 to A08.
Also, any other five
blocks must have numbers selected from A09 to A18, any other five blocks must be from A19 to A27, any
other two blocks
from A28 to A31, and so on.
Note that multiple blocks can have the same teacher number.
- The same teacher must not be in the same class three blocks in a row.
- The same teacher can only put in four blocks at maximum in a row.
Now we have a clear idea of what you want the computer to handle.
STEP 3. Estimate the number of bits required
There is an upper limit to the number of bits the annealing machine can compute.
As you know, an annealing machine is a method that assigns one spin to one element to derive the best
energy for a given
pattern. So we need to know in advance how many elements to set to $+1$ or $-1$.
In this case, there are 40 teachers, 30 periods per week, and 12 classes.
Since the school is to have 12 of these classes in session at the same time, we can assume that $40
\times 12 \times 30 = 14,400$
elements (the pattern of which classes are assigned to each class frame), or spins, are needed to make the
assignments.
Summary
- Verbalize the problem to solve with a computer. (requirements definition)
- Identify what you want the computer to handle.
- Estimate how many spin (corresponding to $+1/-1$ Ising variable) elements are needed
Related Links
ACW Skills Roadmap
Share/Feedback
If you have any comments or suggestions about this page, please feel free to contact us.
We welcome constructive as well as positive feedback. Your feedback will be used to help us improve the site.
Thank you for your valuable feedback.
We look forward to working with you in the Annealing Cloud Web in the future.
Related Articles
-
If you want to know an example of solving a
combinatorial optimization problem with an annealing machine
-
If you want to know an example of solving a
combinatorial optimization problem with an annealing machine
-
If you want to know an example of solving a
combinatorial optimization problem with an annealing machine
-
If you want to know how to use an annealing
machine