Solution Space Analysis and Feasible Genetic Algorithm for Assembly Job-Shop Scheduling Problems
The classical job-shop scheduling problems (JSP) become assembly job-shop scheduling problems (AJSP) if assembly constraints are attached to them. The entire solution space size and the feasible one of AJSP are analyzed and obtained by utilizing combinational mathematics. It is proved that the feasible solution space takes extremely small portion of the entire one. To minimize the makespan of AJSP, genetic algorithm searching in feasible solution space (FGA) is proposed and designed, and the search range of FGA is limited to feasible solution space. Finally, benchmarks tests and results are given which demonstrate the advantage and efficiency of FGA.
Dongming Guo, Jun Wang, Zhenyuan Jia, Renke Kang, Hang Gao, and Xuyue Wang
G.K. Zhao et al., "Solution Space Analysis and Feasible Genetic Algorithm for Assembly Job-Shop Scheduling Problems", Materials Science Forum, Vols. 626-627, pp. 705-710, 2009