REVIEW ON DEVELOPMENT OF META-HEURISTIC BASED SOLUTION FOR JOB SHOP SCHEDULING PROBLEM

The job shop scheduling problem is one of the classical NP-Hard scheduling problem. Very simple special cases of the job-shop problem are already strongly NP-hard. An instance with ten jobs to be processed on ten machines formulated in 1963 was open for more than 25 years. In this paper we discuss a prominent approach to solve job shop scheduling problem based on Ant Colony Optimization. The ACO algorithm is developed using artificial ants. The Ant System in ACO takes its cue from the nature inspired insect that is the working scenario of ants and the quality of attractions towards the pheromone trails excreted by the ants of the previous iteration. Moreover the pheromone (hormone) excreted by the ants gets evaporated progressively by the passage of time, so the path with the highest pheromone deposition till the end of iteration will be the best solution for the ants to follow to reach for the target.