Abstract— Scheduling is the most important issue to be solved in the real time environment. One such emerging problem in the scheduling is the job shop scheduling problem, applied in various fields of engineering. The Job Shop Scheduling Problem (JSP) is one of the hardest combinatorial optimization problems. The performance of schedules released to a shop floor may greatly be affected by unexpected disruptions. The main objective of the JSP is to find a schedule of operations that can minimize the maximum completion time (called makespan) that is the completed time of carrying total operations out in the schedule of n jobs and m machines. Recently many works have been reported to reduce the makespan time in JSP. No Scheduling technique has guaranteed optimality. This paper aims at providing a well optimized scheduling technique; minimize the makespan, process time and the number of iterations. This paper proposes a Genetic algorithm with Unordered Subsequence Exchange cross-over (USXX) and Hybrid approach called a PSO-GA. This algorithm is a stochastic procedure that uses a population of solution, called particles, which move in search space. Using the special cross over technique USXX the most of the benchmark results are compared and obtain the results near to optimal value of the benchmark problems. The hybrid approach produced the better computational time compare to the GA. This approach is also applied to maximize net present value. Multiple runs of both algorithms are performed and the results are averaged in order to achieve meaningful comparisons. These finding are very promising and demonstrate the applicability of this hybrid approach for this existing problem.

Index Terms— Job Shop Scheduling Problem (JSP), Makespan, Genetic algorithm, Particle swarm optimization

Cite: T Varun Kumar and B Ganesh Babu, " Optimizing of Makespan in Job Shop Scheduling Problem: A Combined New Approach," International Journal of Mechanical Engineering and Robotics Research, Vol. 3, No. 2, pp. 44-53, April 2014.