Open Access Open Access  Restricted Access Subscription or Fee Access

Genetic Algorithm and Ant Colony Optimization for Optimizing Combinatorial Fuzzy Job Shop Scheduling Problems

P. Surekha, S. Sumathi

Abstract


In this paper, we present a genetic algorithm and ant colony optimization algorithm for solving the Job-shop Scheduling Problem (JSSP). The genetic algorithm generates the initial population, selects the individuals for reproduction creating new individuals. Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of ants, used to solve this combinatorial optimization problem. In JSSP ants move from one machine (nest) to another machine (food source) depending upon the job flow, thereby optimizing the sequence of jobs. The sequence of jobs is scheduled using Fuzzy logic and optimized using GA and ACO. The makespan, completion time, makespan efficiency, algorithmic efficiency and the elapsed time for the genetic algorithm and the ant colony algorithm are evaluated and compared. Computational results of these optimization algorithms are compared by analyzing the JSSP benchmark instances, FT10 and the ABZ10 problems.


Keywords


Job Shop Scheduling Problem, Makespan, Planning, Scheduling, Genetic Algorithm, Ant Colony Optimization

Full Text:

PDF

References


A. Coelle, Tellez-Emiquez, E., Mezura-Montes, E., "An Ant System with steps counter for the Job Shop Scheduling Problem." IEEE Congress on Evolutionary Computation, Sept. 2007, pp. 477-484.

Marco Dorigo, Gambardella, L.M., "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem" IEEE Transactions on Evolutionary Computation, vol 1., pp. 53-66, Apr. 1997.

Didier Dubois, Hélène Fargier, Henri Prade, "Fuzzy constraints in job-shop scheduling." Journal of Intelligent Manufacturing, vol. 6, no. 4, pp. 215-234, 1993.

J. Christopher Beck, Patrick Prosser and Evgeny Selensky, "Graph Transformations for the Vehicle Routing and Job Shop Scheduling Problems." In Graph Transformation, Germany: Springer-Verlag, pp. 60-74, 2002

Jun Zhang, Xiaomin Hu, X. Tan, J.H. Zhong and Q. Huang, "Implementation of an Ant Colony Optimization for job shop scheduling problem." Transactions of the Institute of Measurement and Control, pp. 93-108, 2006.

Daniel Merkle, Martin Middendorf, "An Ant Algorithm with a new pheromone evaluation rule for total tardiness problem." Real World Applications of Evolutionary Computing, Springer, vol.1803, pp. 287-296, 2000.

Pezzella F., Morganti G., Ciaschetti G., "A genetic algorithm for the Flexible Job-shop Scheduling Problem." Computers and Operations Research, Elsevier Science Ltd., vol. 35, pp. 3202-3212, 2008.

Fevrier Valdez, Patricia Melin ,Olivia Mendoza, [2008] “A new evolutionary method with fuzzy logic for combining particle swarm optimization and Genetic algorithm: the case of neural networks optimization”, IEEE Int. Conf. On Neural Networks, pp. 1536-1543, June 2008.

Giffler, B., Thompson,G.L., "Algorithms for solving production scheduling problems. Operations Research" Operations Research, vol. 8, pp. 487-503, 1960.

Brooks, G.H., White,C.R., "An algorithm for finding optimal or near optimal solutions to the production scheduling problem" Journal of Industrial Engineering, vol. 16, pp. 34-40, 1965.

John H. Blackstone, Don. T. Philips, Gary L. Hogg, “A state-of-the-art survey of dispatching rules for manufacturing job-shop operations." International Journal of Production Research, vol. 20, pp. 27-45, Jan 1982.

Cheng R., Gen M., Tsujimura,Y., “A tutorial survey of job-shop scheduling problems using genetic algorithms”, Computers and Industrial Engineering, vol 30, pp. 983-997, 1996.

Xiaoyu Song, Limei Sun, Qiuhong Meng, “Deadlocks solving strategies in hybrid PSO algorithm for job shop scheduling” IEEE Proc. of the Int. Conf. on Natural Computation , pp. 614-618, Nov. 2008.

Alok D Innani., “Applying Data Mining to Job Shop Scheduling Problems using Regression Analysis”, Ph.D Dissertation, Department of Industrial and Manufacturing Systems Engineering, Ohio University, Japan, August 2004.

Jain.A.S, Meeran.S, “Deterministic Job-Shop Scheduling:Past,Present and Future”, European Journal of Operational Research, vol. 113(2), pp.390-434, March 1999.

Li Xiaoping, “Solving Job Shop Scheduling Problem using Demarcation-Genetic algorithm”, Electric Machines and control, vol. 3(2), pp. 93-96, 1999.

http://www.swarmintelligence.org

http://www.aco-metaheuristic.org

http://people.brunel.ac.uk/


Refbacks

  • There are currently no refbacks.