Shuichi FUKUDA (FicyTechnology, NTT Docomo)
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.
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.
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) | |||
・ | ||||||||||||
・ | ||||||||||||
・ |
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.
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.
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.
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.