Job-shop scheduling using genetic algorithm

Job-shop scheduling, a typical NP-complete problem, is an important step in planning and manufacturing control of CIMS environments. Researches on job-shop scheduling focus on knowledge-based approaches and heuristic searching which are useful apart from the difficulty of obtaining knowledge. Genetic algorithms are optimization methods which use the ideas of the evolution of nature. Simple as genetic algorithms are, they are efficient. Three novel genetic algorithms models, such as decimal idle time coding genetic algorithms (DITCGA), binary idle time coding genetic algorithms (BITCGA), and adaptive idle time coding genetic algorithms (AITCGA), are presented to design a job-shop scheduling algorithm in this paper. Using the idle processing time to code this problem, we efficiently reduce the solution space. In our approaches, an adaptive learning mechanism is applied to guide the searching or evolution process. The simulation results show the efficiency of these approaches