Developing a job shop scheduling system through integration of graphic user interface and genetic algorithm

摘要

Job shop scheduling problem is one of the well known hardest combinatorial optimization problems that has a wide range of industrial application domains. Due to the NP-hardness of job shop scheduling problem, meta heuristic search methods such as genetic algorithm have been widely applied to find the good schedules, however, solving the precedence constrained sequencing problems such as JSP is still challenging for genetic algorithms. Moreover, the genetic algorithms for the precedence constrained sequencing problems have been often problem dependent or constraint specific, and the user experiences are not considered in developing them. To address these issues, this paper aims to develop a graphic user interface based job shop scheduling system that searches the good schedules by using the candidate order based genetic algorithm. The candidate order based genetic algorithm enable our scheduling system to handle a wide range of precedence constrained sequencing problems conveniently, and the users can construct various sequencing problems via simple graphic user interfaces. For illustration, our system is applied to classical JSP and its variant, and the experiment results reveal the promising applicability of the system.