A new heuristic algorithm to determine more than one sequence in permutation flow shop scheduling by using harmonic triangle

In this paper we present a new heuristic algorithm to minimize the total completion time (Makespan) in permutation flow shop scheduling of ‘n’ jobs and ‘m’ machines by using harmonic triangle.
Nội dung trích xuất từ tài liệu:
A new heuristic algorithm to determine more than one sequence in permutation flow shop scheduling by using harmonic triangleInternational Journal of Mechanical Engineering and Technology (IJMET)Volume 10, Issue 03, March 2019, pp. 284-289. Article ID: IJMET_10_03_029Available online at http://www.iaeme.com/ijmet/issues.asp?JType=IJMET&VType=10&IType=3ISSN Print: 0976-6340 and ISSN Online: 0976-6359© IAEME Publication Scopus Indexed A NEW HEURISTIC ALGORITHM TODETERMINE MORE THAN ONE SEQUENCE INPERMUTATION FLOW SHOP SCHEDULING BY USING HARMONIC TRIANGLE B. Dhanasakkaravarthi Research Scholar, Sathyabama Institute of Science and Technology, India, Chennai-119 Dr. A.Krishnamoorthy Professor, School of Mechanical Engineering, Sathyabama Institute of Science and Technology, India, Chennai-119 ABSTRACT In this paper we present a new heuristic algorithm to minimize the total completion time (Makespan) in permutation flow shop scheduling of ‘n’ jobs and ‘m’ machines by using harmonic triangle. In any shop floor, the major responsibility of process planning engineer is to process the ‘n’ number of jobs in ‘m’ machines within the due date. It can be achieved by optimal sequence of processing the jobs. Many classical heuristics procedures were proposed starting from Johnson’s algorithm to find optimal or near optimal sequence for job completion.In this research, an attempt is made to propose a new heuristic by using Harmonic triangle. Also, the new heuristic is compared with fewother popular heuristics like CDS, Palmer, RA and Gupta Heuristics and the efficacy of new heuristic is analysed. Keywords Permutation Flow shop Scheduling, Heuristics, Harmonic Triangle,Sequencing. Cite this Article B. Dhanasakkaravarthi and Dr. A.Krishnamoorthy, A New Heuristic Algorithm to Determine More Than One Sequence in Permutation Flow Shop Scheduling By Using Harmonic Triangle, International Journal of Mechanical Engineering and Technology, 10(3), 2019, pp. 284-289. http://www.iaeme.com/IJMET/issues.asp?JType=IJMET&VType=10&IType=31. INTRODUCTIONIn flow shop scheduling the performance of the processing of „n‟ jobs with „m‟ machines isevaluated by multiple criteria, like make span, lateness, earliness (EDD), average time of jobsin machines. The main objective of our research is focused to find the sequence of jobs toreduce the total completion time (Makespan) by using harmonic triangle. Johnson‟s [1]proposed an algorithm to find the optimal solution for 2 machines with „n‟ jobs and further http://www.iaeme.com/IJMET/index.asp 284 editor@iaeme.com A New Heuristic Algorithm to Determine More Than One Sequence in Permutation Flow Shop Scheduling By Using Harmonic Trianglethis algorithm is extended for 3 machines with „n‟ jobs. The condition for extended Johnson‟salgorithm for 3 machines is: If mini ti1 ≥ max I ti2 (Or) If mini ti3 ≥ max I ti2 If any one condition is satisfied, the 3 machines problems are converted to 2 machineswith „n‟ jobs.The problem of minimizing the makespan is NP hard, therefore certainassumptions are made given by Baker[2]:  All the jobs are independent and available processing time is zero initially  All the machines are readily available  All the jobs are processed at each machine at one time  Pre-emption is not allowed. Many classical heuristics have been developed to optimize the make span in permutationflow shop scheduling problem. [3] Palmer proposed the slope index method to find the nearoptimal solution. Campbell [4] proposed the CDS and RA algorithmwas proposed byDannenbring [5] to minimize the makesspan and they resemble greatly the Johnson‟salgorithm. In real situations, NEH [6] algorithm proposed by Nawaz et al. gives the betterperformance than any other heuristic. Baskar and Anthony Xavior [7, 9, 11] proposed a fewnew heuristic algorithmsone based on the Pascal‟s triangle, another based on dummymachines and few more variants of NEH. They analysed the heuristics to determine thesequence for minimizing the make span in FSSP using Taillard [8] and Vallada‟s [10]problems. In this paper we propose a new heuristic based on Harmonic triangle and analysedthe algorithm using two problems, one with 4 jobs and 4 machines and the other with 10 jobsand 10 machines.2. HARMONIC TRIANGLEHarmonic triangle is similar to Pascal‟s triangle and the rule for generating the harmonictriangle is by adding two consecutive entries to give the entry between them in the row above.To get the next term, subtract the next term from the corresponding term on the row above.Moreover, it is possible to work downwards row by row because the entry at the left hand endof the nth row is 1/n. The entries in the harmonic are similar to Pascal‟s triangle,involving thebinomial coefficients. The harmonic triangle for rth entry in the nth row is given by: 0Hr 1/1 1Hr 1/2 1/2 2Hr 1/3 1/6 1/3 3Hr 1/4 1/12 1/12 1/4 4Hr 1/5 1/20 1/30 1/20 1/5 5Hr 1/6 1/30 1/60 1/60 1/30 1/6 Mathematically, ( ) ( )( ) H(n,r) = ( )( ) ( ) = The formula for harmonic triangle is given by: H (n, r) + H (n,r+1) = H(n-1,r) http://www.iaeme.com/IJMET/index.asp 285 editor@iaeme.com ...