Theme
In this 2023 IPA MITOU Target Program, I worked on developing a service that automates the scheduling of
class shifts for students and instructors at private tutoring schools (scheduling tasks). In private tutoring
schools, scheduling tasks for the summer vacation period can take several days to several weeks. These are
burdensome tasks, but automation has not progressed due to the vast number of possible combinations. I
challenged if this issue could be resolved using annealing technologies.
Details of the combinatorial optimization problems
This is a task assignment problem between instructors and students in private tutoring schools. In private
tutoring schools, each school has a set limit on how many students one instructor can handle per session. From
the perspectives of operating costs and profits, many schools aim to assign as many students as possible to
each instructor. This time, we developed a service that schedules sessions while considering factors such as
the compatibility between students and instructors and allowing both to attend consecutive sessions, all while
minimizing the cost for instructors.
Decision variables
Five-demensional decision variables, Instructor x Subject x Student x day x slot (1 if the class is
conducted, 0 if not)
Image of decision variables
|
Date & Slot |
Apr/1 |
Apr/2 |
Student |
Class |
Instructor |
14:00 |
15:00 |
16:00 |
17:00 |
18:00 |
19:00 |
20:00 |
14:00 |
15:00 |
・・・ |
Student0 |
Math |
A |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
B |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
C |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
D |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
E |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
Science |
A |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
B |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
C |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
D |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
E |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
English |
A |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
B |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
q (0 or 1) |
|
・ |
|
|
|
|
|
|
|
|
|
|
・ |
|
|
|
|
|
|
|
|
|
|
・ |
|
|
|
|
|
|
|
|
|
|
Objective function
- Minimize the cost of instructor
- Enable instructors and students to attend consecutive sessions
- Compatibility between students and instructors
- Avoid scheduling student classes on consecutive days, etc.
Constraints
- Conduct classes for the number of sessions applied for by the student
- Classroom space
Challenges
In this problem set, although minimizing instructor costs is the primary condition, I also need to consider
elements essential to the actual operation of the school, such as assigning consecutive sessions to
instructors and the compatibility between students and instructors. Therefore, I faced challenges in adjusting
the coefficients for multi-objective optimization. I designed the system to normalize the values of each
objective function to the same scale, allowing the school to adjust the weights of the factors relative to
instructor costs.
Future Outlook
I plan to have more schools use it on a trial basis and improve the product further. With the current
formulation, the problem becomes unsolvable as its scale increases. Therefore, I believe it is necessary to
reduce the number of decision variables by more effectively utilizing zero-filling and one-filling, and also
consider problem decomposition.
Achievements / Gratification
Fixstars Amplify provides both middleware and solvers, and it is available for free trials to all users. This
makes it very easy to get started with quantum annealing if you're interested. As middleware, it allows easy
access to other solvers as well, which was very helpful for the benchmarks.
To Viewers
Combinatorial optimization problems require expertise in formulation and coding. However, once a "template"
is created, valuable results can be generated by feeding the data you own or the results predicted by machine
learning into this template. I strongly encourage many people to try these. I hope this technology spreads not
as a difficult, hard-to-approach technology, but as a mechanism where valuable results overflow simply by
feeding in data! Here is the link for the website I developed this time. Please have a look if you get a
chance!
https://ficy-tech.com/aboutzyukukoma
* All information in this article is based on information available at the time of the interview.