Open Access Open Access  Restricted Access Subscription or Fee Access

Planning, Scheduling and Optimizing Job Shop Scheduling Problem Using Genetic Algorithm

P. Surekha, P.RA. Mohana Raajan, Dr.S. Sumathi

Abstract


Evolutionary algorithms are having a leading focus in solving several optimization problems. Job-shop scheduling problem (JSSP) is one among the common NP-hard combinatorial optimization problems used to allocate machines for a set of jobs over time and hence optimizing the processing time, waiting time, completion time, and makespan. In this paper an eminent approach based on the paradigm of evolutionary computation for solving job shop scheduling problem is proposed. The solution to the problem is alienated into three phases; planning, scheduling and optimization. Initially, the jobs are scheduled, in which the machines and jobs with respect to levels are planned. Scheduling is optimized using Genetic Algorithm (GA), which is a powerful search technique, built on a model of the biological evolution. Like natural evolution GA deal with a population of individuals rather than a single solution and fuzzy interface is applied for planning and scheduling of jobs. The Fisher and Thompson 10x10 instance (FT10) problem is selected as the experiment problem and the algorithm is simulated using the MATLAB R2008B software.

Keywords


Job Shop Scheduling Problem, Genetic Algorithm, Fuzzy logic, FT10, Makespan

Full Text:

PDF

References


Fevrier Valdez, Patricia Melin ,Olivia Mendoza, “A new evolutionary method with fuzzy logic for combining particle swarm optimization and Genetic algorithm: the case of neural networks optimization”IEEE,2008.

Xiaoyu Song ,Limei Sun ,Qiuhong Meng“Deadlocks solving strategies in hybrid PSO algorithm for job shop scheduling”IEEE,2008.

Eberhart R, Kennedy J, “A New Optimizer Using Particles Swarm Theory ”,Proc Sixth International Symposium On Micro Machine And Human Science, Japan: IEEE Service Center,1995,pp39-43.

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

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

Cheng R , Gen M, “A tutorial survey of job-shop scheduling problems using generic Algorithm-I representation”, Computers and industrial engineering, 1996,30(4):pp983-997.

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.

Prof.Dr.J.Kaschel, Dr.T.Teich,G. Kobernik, B.Meier, “Algorithm for the Job Shop Scheduling Problem- a comparison of different methods” Chemnitz, Germany.

Mahanim Omar, Adam Baharum,Yahya Abu Hasan , “A job shop scheduling using genetic algorithm”, proceedings of the 2nd IMT-GT Regional Conference on Mathematics, Statistics and Applications, june 13-15,2006.

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


Refbacks

  • There are currently no refbacks.