# Development of “zyuku-koma”, an automatic scheduling app for private tutoring schools

###### Member

Shuichi FUKUDA (FicyTechnology, NTT Docomo)

##### 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!