Research on job-shop scheduling problem based on genetic algorithm |
| |
Authors: | Zhenyuan Jia Jiangyuan Yang Defeng Jia |
| |
Affiliation: | Key Laboratory for Precision and Non-traditional Machining Technology of Ministry of Education , Dalian University of Technology , Dalian 116024, China |
| |
Abstract: | With job-shop scheduling (JSS) it is usually difficult to achieve the optimal solution with classical methods due to a high computational complexity (NP-hard). According to the nature of JSS, an improved definition of the JSS problem is presented and a JSS model based on a novel algorithm is established through the analysis of working procedure, working data, precedence constraints, processing performance index, JSS algorithm and so on. A decode select string (DSS) decoding genetic algorithm based on operation coding modes, which includes assembly problems, is proposed. The designed DSS decoding genetic algorithm (GA) can avoid the appearance of infeasible solutions through comparing current genes with DSS in the decoding procedure to obtain working procedure which can be decoded. Finally, the effectiveness and superiority of the proposed method is clarified compared to the classical JSS methods through the simulation experiments and the benchmark problem. |
| |
Keywords: | job-shop scheduling genetic algorithm decode select string decoding assembling work |
|
|