Per the hackathon’s premise, participants had to help rebuild the Empire’s military might after the destruction of the first Death Star. For that purpose, they were put in charge of a factory on the outskirts of the Galaxy. Teams had to decide on the plant’s schedule and decide how long this or that industrial machine would need to be used in order to restore the Empire’s strength as fast and cheap as possible.
The task is complicated by a number of other conditions, explains ITMO team member Viktor Khovansky. For one, the factory only has 13 work teams; some complete tasks faster, but ask for more pay; others are cheaper and come in greater numbers, but work slow. It was also necessary for the teams to take into account the specifics of each production device: some parts cannot be manufactured until others have been made. Penalties were given out for failures; for example, the schedule might indicate that it is time to construct battle droids, but the metal needed to produce them hasn’t been delivered yet. It was also important to avoid situations where two work teams end up coming in to use the same device at the same time, or, inversely, if some equipment is left idle – such situations increase the costs of production, which is highly disadvantageous to the Empire during a crisis.
ITMO's team Traffox
Strategic decisions had to be made, too, like which droids to use, how to use them and for what purpose. For example, one could assign welder droids to a specific task or give the task to a production line, which works on several orders of the same type simultaneously. What this means is that, for the same cost, a droid will produce a single part quickly or a production line will produce 10 parts at once, but will take longer to do so.
“The plant’s production schedule had to be optimized to reduce the construction time and cost of the new Death Star. We only had a limited amount of funds – 10,000 galactic credits – and resources, e.g. work teams, production devices, etc. In addition, one third of our final evaluation grade depended on the quality of our presentation to the jury,” – comments another ITMO team member, Vyacheslav Shalamov.
The factory’s production schedule was to be represented using Gantt charts – a popular format for presenting plans and schedules using bar graphs. As visual aids, they could be used to show which work teams would complete which tasks and when. The charts were checked for inconsistencies by experts from the hackathon’s organizer, the LenPoligrafMash holding. As the jury included only a single technical specialist, most attention was given to the visual aspect. In the initial stages, it was important that the teams show a working solution, even if it’s not the most optimal.
Team Traffox with their award
“At first, we tried to make everything as algorithmically and mathematically precise as possible – we even started to develop a mathematical solution to the problem -, but then we learned that this isn’t that important in the early stages. What did matter is developing a solution quickly. And so we developed a heuristic algorithm, meaning that it wouldn’t be 100% precise, but it would do the most important things. One thing about the hackathon is that everyone could only submit a solution once, which is why we built an automatic schedule verifier to check for mistakes. At the same time we wrote unit tests to check our algorithms,” – tells us Viktor Khovansky.
One of the advantages ITMO University’s team had was their use of precise mathematics, which was also noted by the experts. As the jury deemed it, their algorithm was the most well-done in terms of its architecture. Moreover, their solution is, in essence, universal, meaning that the fictional factory data can be replaced with that of the employees and resources of any other real-life enterprise and the program will be able to provide an effective, cost-cutting solution.
As the ITMO students explain, the jury members were surprised to see that some of the teams had decided to solve the problem using not programming methods, but through substitution, collating and graphs. Still, there’s room for improvement for the hackathon, too; for one, the starting data was given to the participants on paper and not in digital format, meaning that they had to spend quite some time on simply retyping it onto their computer. Next year, the organizers plan to give more weight to the solutions’ algorithmic aspect during evaluation.
“The hackathon was really useful in that we were able to quickly learn about the theory and practice of scheduling theory. This is one subset of mathematics that we haven’t had the chance to learn about in university,” – notes member of team Traffox Evgeny Varlamov.
ITMO University’s team, which also included students Sergey Menshov and Javlon Isomurodov, placed third on the hackathon’s leaderboard. The second place went to the team “Exception to the Rule” from the St. Petersburg Mining University, while the first place was taken by the “Eastern District” team from the Mozhaysky Military Space Academy. Jury members expressed that the winners have provided correct results throughout the event and made no mistakes in none of the tasks, even providing the optimal solutions to two of them.
