# Complementing Solutions to Optimization Problems via Crowdsourcing on Video Game Plays
## Implementation
### Game 1: Scheduling Problems
#### 3.2.2 Game Description  
In all our three scheduling problems, a complete schedule is shown via a single common visualization and interface, leaving only small differences in the moves available to the playersfor each variant. In the implementation of the game, we were inspired by the 1982 puzzle video game Tetris, designed by [PERSON]. In Tetris, a player is given control of a collection of falling tetrominoes; that is shapes constructed from four square tiles. There, the goal of a player is to timely pack the tetrominoes on a rectangular board, while minimizing the height of the resulting pile of tiles. By contrast, in our game, a player controls one job at a time, aiming at minimizing the length of the schedule, so-called the _makespan_. The video game puts up three consecutive stages, one for each of three scheduling problems, namely: identical parallel machines, open shop scheduling, and job shop scheduling. They are as follows:  
**Identical Parallel Machines (IPM):**: Players must schedule a job consisting of a single task and need only assign the task to a machine. The task can be moved from one machine to other. Figure 1 convey the user interface of all our three scheduling games. In particular, Figure 1a,b give the player interface for IPM for m = 5 and m = 7, respectively. Despite its simplicity, this version of IPM is not solvable in polynomial time, as can be verified in Reference [35]. **Job Shop Scheduling (JSS):**: Players must deal with a job consisting of multiple tasks, one for each machine. Players can choose the machine (a column) to which a task is assigned; however, tasks have to observe a chronological ordering constraint for completion. The game controls allow players to switch a task between machines; hence, users can select the most appropriate machine where to execute a task. Figure 1c,d show the user interface for JSS for m = 5 and m = 7. **Open Shop Scheduling (OSS):**: Players must schedule a job consisting of multiple tasks, one for each machine. Players may choose the chronological order for task execution; however, they have no control as to which machine should process a task. The game interface enables the move of a task to the end of a task queue, enabling players to arrange task execution as they wish. Figure 1e,f show the user interface for a player to solve OSS for m = 5 and m = 7. On each playthrough, every participant has to play these three games, consecutively. Each scheduling variant is preceded with a tutorial, giving the user a chance to adapt to the game controls. Figure 1: User interface for the scheduling game. Here, (**a**,**b**) show the Identical Parallel Machines variant; (**c**,**d**) the Job Shop Scheduling problem variant; and, finally, (**e**,**f**) show the Open Shop Scheduling problem variant. User Interface Design, Gameplay and Playtesting  
The User Interface (UI) design resembles a timetable, or a Gantt chart rotated by 90 degrees, with the time axis running vertically. Each column is assigned a different color to ensure that the players can distinguish them. Falling blocks, that is, tasks that can be controlled by the player at a given time point, have different colors depending on the column in which they are highlighted. Additionally, tasks move downward at a steady pace, giving the player a time limit for choosing the columns in which to place them. A horizontal line stretching across the columns shows the maximum height of all of the piles of blocks, communicating to the player what should be minimized and how well they are doing, both visually and by their numeric score. This design is illustrated in Figure 1.  
The game for solving scheduling problems consists of a succession of quick levels. The three different stages are played consecutively, with one tutorial level at the start of each stage. Jobs are randomly generated for each level, with a length of exponential distribution.