Towards the generation of heuristics for the Job Scheduling Problem via Crowd Computing: A video game approach
Export citation
Abstract
This thesis was conducted for the Master’s in Computer Science Program within the research line of Bio-inspired algorithms with the objective of demonstrating that heuristics for the Job Shop Scheduling Problem (JSSP) can be generated from strategies used by humans when solving the same type of problem, and that this can be done by crowdsourcing using video games. Heuristics are discussed in the computer science field and the psychological field. In both, a heuristic is a quick strategy for decision making when solving a problem which gives up the accuracy of the solution in exchange for obtaining an answer faster. Given that humans tend to use heuristics naturally, an analysis of their behavior can be done to identify these heuristics. The JSSP is an optimization problem within the Scheduling domain where different jobs, composed of activities of different types, must be completed by assigning each of them a position in time in any of the different available machines that are of the same type than the activity, with the intention of finalizing all jobs in the minimum time possible. Scheduling problems including the JSSP are seen in many manufacturing processes and supply chain systems, making them of high interest for companies. Computationally, the JSSP is a hard problem of non-deterministic polynomial time (problems that in order to find the optimal answer, a large amount of computational time is required, making it unfeasible to find a solution when these problems are large) which is why techniques like heuristics are needed to solve big versions of this problem. If people are given the JSSP, in many cases, they will naturally start using heuristics to try to solve it. With this in mind, an analysis designed for identifying heuristics was applied on the behavior of 21 individuals when solving the JSSP.
Crowdsourcing is the use of external people to a project in which the intention is to obtain goods or, in our case, data from a group of participants. In this thesis, the generation of data from humans solving JSSPs was crowdsourced using a video game by making people to solve JSSPs inside the game. For this, different JSS problems were gamified, which means to add typical elements of a game like points and score to an activity, so these could be presented as features in a video game. The gamification of activities has been proven to motivate and increase engagement from the participants, being an important factor that influenced the use of a video game for this thesis. A video game that included the gamified JSSPs was given to play to 21 students. The movements that the players used to solve the JSSPs while playing were collected to be later analyzed. This research shows how video games can be used to gather data from humans when solving JSSPs, and then transforming those solution processes into heuristics by using Machine Learning (ML) algorithms.
Machine Learning algorithms use experience to create models that simulate a behavior and make decisions, which means that analyzing the movements of human players will create methods intended to emulate their behavior. In order to complete this project, first, experimentation was made on ML algorithms to test their capacity to replicate the behavior of existing heuristics in the literature by training ML models with data generated using those heuristics and under different scenarios. ML algorithms used to create the models were: Decision Trees, Multi-Layer Perceptron, K-neighbors Algorithm, Support Vector Machines and Random Forest Algorithm. After knowing the effectiveness of training and testing these ML algorithms, Decision Trees, Support Vector Machines and Random Forest Algorithms were selected as the better algorithms for continuing the research, and then used to train models with the data collected from the players of the video game. An analysis was conducted on the accuracy on the ML algorithms emulating the players, and aiming at understanding their behavior and strategies for solving problems that can be used as heuristics. The behavior of the ML models were visualized and interesting patterns on how humans solved the JSSP were detected, and promising results were obtained. Some of the heuristics obtained from humans were compared against common heuristics, and interesting conclusions were drawn. This thesis provides the initial steps for generating heuristics from humans when solving difficult computational problems, and leaves and open space for future research to enhance and produce new solution models.