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

Chia sẻ: Nguyễn Thảo | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

16
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 (IJMET) Volume 10, Issue 03, March 2019, pp. 284-289. Article ID: IJMET_10_03_029 Available online at http://www.iaeme.com/ijmet/issues.asp?JType=IJMET&VType=10&IType=3 ISSN Print: 0976-6340 and ISSN Online: 0976-6359 © IAEME Publication Scopus Indexed A NEW HEURISTIC ALGORITHM TO DETERMINE MORE THAN ONE SEQUENCE IN PERMUTATION 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=3 1. INTRODUCTION In flow shop scheduling the performance of the processing of „n‟ jobs with „m‟ machines is evaluated by multiple criteria, like make span, lateness, earliness (EDD), average time of jobs in machines. The main objective of our research is focused to find the sequence of jobs to reduce 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 Triangle this algorithm is extended for 3 machines with „n‟ jobs. The condition for extended Johnson‟s algorithm 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 machines with „n‟ jobs.The problem of minimizing the makespan is NP hard, therefore certain assumptions 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 permutation flow shop scheduling problem. [3] Palmer proposed the slope index method to find the near optimal solution. Campbell [4] proposed the CDS and RA algorithmwas proposed by Dannenbring [5] to minimize the makesspan and they resemble greatly the Johnson‟s algorithm. In real situations, NEH [6] algorithm proposed by Nawaz et al. gives the better performance than any other heuristic. Baskar and Anthony Xavior [7, 9, 11] proposed a few new heuristic algorithmsone based on the Pascal‟s triangle, another based on dummy machines and few more variants of NEH. They analysed the heuristics to determine the sequence 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 analysed the algorithm using two problems, one with 4 jobs and 4 machines and the other with 10 jobs and 10 machines. 2. HARMONIC TRIANGLE Harmonic triangle is similar to Pascal‟s triangle and the rule for generating the harmonic triangle 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 end of the nth row is 1/n. The entries in the harmonic are similar to Pascal‟s triangle,involving the binomial 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
B. Dhanasakkaravarthi and Dr. A.Krishnamoorthy 3. PROPOSED HEURISTICS BASED ON HARMONIC TRIANGLE The new heuristic for minimization of make span can be revealed by considering the example given [12] by Panneerselvam as shown in Table 1. There are 4 jobs to be processed with 4 machines with minimum job completion time. Before adopting this procedure, Gupta‟s heuristic gives the solution by converting the 4 machines into a 2 machine problem. He added first 3 machines and makes it as a single machine and the last machine is left out to get the first machine. For obtaining second machine, the first machine is left out and added the remaining machines. Finally,Johnson‟s multistage rule is applied to find the sequence. Table 1 .Four Machine problem Processing time in machine Job I II III IV 1 4 3 7 8 2 3 7 2 5 3 1 2 4 7 4 3 4 3 2 Let us now explain the procedure using the numeric example for the new heuristic as follows: Step 1 4 jobs are to be processed in 4 machines by assuming that all the jobs are available with zero processing time. ie, here n=4, m=4. Step 2 By using Harmonic triangle,select (m-2)Hr [3] , the elements are; 1/3,1/6,1/3. Step 3 Now, the machining times are multiplied with harmonic triangle elements as selected in the earlier step and added together. For example: t11 = 1/3(4) + 1/6(3) +1/3(7), last machine time is left out (i.e., 8) t12 = 1/3(3) + 1/6(7) +1/3(8), first machine time is left out (i.e., 4) Similarly, for all the remaining jobs with processing time t21,t22,t31,t32,t41 & t42can be computed. Step 4 Now, the problem is reduced to 4 jobs with 2 machine problem and Johnson‟s algorithm is used to find the sequence and corresponding makespan for the given problem. Calculate all the job timings t11 to t42: t11 = 1/3(4) + 1/6(3) +1/3(7) = 25 t12 = 1/3(3) + 1/6(7) +1/3(8) = 29 t21 = 1/3(3) + 1/6(7) +1/3(2) = 17 t22 = 1/3(7) + 1/6(2) +1/3(5) = 26 t31 = 1/3(1) + 1/6(2) +1/3(4) = 12 t32 = 1/3(2) + 1/6(4) +1/3(7) = 22 t41 = 1/3(3) + 1/6(4) +1/3(3) = 16 t42 = 1/3(4) + 1/6(3) +1/3(2) = 15 http://www.iaeme.com/IJMET/index.asp 286 editor@iaeme.com
A New Heuristic Algorithm to Determine More Than One Sequence in Permutation Flow Shop Scheduling By Using Harmonic Triangle Step 5 Now, the processing sequence can be obtained by using Johnson‟s Algorithm, because the 4 machine problem is reduced to 2 machine problem and given in Table 2. Table 2 .Two machine problem Processing time in machine Job I II 1 25 29 2 17 26 3 12 22 4 16 15 Based on Johnson‟s Algorithm, the sequence obtained is 3-2-1-4 with a make span of 31 units.Now, consider a random problem with 10 jobs to be processed in 10different machines (Table 3). In this case n=10 and m=10. In this problem, we select (m-2)Hr = 8H8 and the corresponding harmonic triangle elements are 1/9, 1/72,1/252,1/504,1/630,1/504,1/252,1/72,1/9. Now, the problem is reduced to 10 jobs with 2 machines by following the same procedure as in earlier example as shown in Table 4. Table-3 Example of 10 jobs and 10machines Job M/c1 M/c2 M/c3 M/c4 M/c5 M/c6 M/c7 M/c8 M/c9 M/c10 1 5 2 3 5 7 9 7 8 2 7 2 2 6 4 2 6 2 5 2 6 1 3 1 2 2 1 3 7 2 5 4 4 4 7 5 6 3 2 3 2 4 2 2 5 6 6 1 8 6 4 3 9 6 4 6 3 7 5 2 2 1 5 3 2 6 7 7 2 4 6 5 5 1 2 5 2 8 5 1 7 1 7 3 6 6 2 2 9 7 8 6 9 1 8 2 1 6 6 10 4 3 5 8 3 1 3 8 3 7 Table 4. 10 Machines reduced to Two Machines Job M/c1 M/c2 1 2256 2931 2 2654 2413 3 1737 2003 4 2953 2402 5 4009 3276 6 1873 3974 7 3625 1565 http://www.iaeme.com/IJMET/index.asp 287 editor@iaeme.com
B. Dhanasakkaravarthi and Dr. A.Krishnamoorthy 8 2383 1302 9 4125 4487 10 2482 3274 The computations are carried out taking the same denominator while adding the weighted machining times. Now, the problem is reduced to „n‟ jobs „2‟ machine similar to Johnson‟s algorithm with the sequence obtained is 3-6-1-10-9-5-4-2-7-8 with a make span of 96 units. 4. COMPARISON OF OTHER HEURISTICS The performance is compared with other classical heuristics and presented in Table 5. Table 5. Comparison of Performance Algorithm Sequence Make span Palmers slope index 3-1-10-5-6-2-8-7-9-4 99 Gupta‟s Heuristics 3-6-10-1-5-9-8-2-7-4 103 RA Heuristics 3-10-1-5-9-8-6-2-7-4 97 CDS Heuristics 3-6-10-1-9-5-8-2-7-4 102 Baskar Heuristic (by using Pascal‟s Triangle) 3-8-1-5-9-7-2-10-4-6 103 Proposedalgorithm (by Harmonic triangle) 3-6-1-10-9-5-4-2-7-8 96 It is observed that the make span determined by the new heuristic is found to be better when compared with any other heuristic. RA heuristic is a close runner with a make span of 96 units. The make span deviation for the better solution is (103-96)/ 96 = 7.2%, which is significant. 5. CONCLUSION In this paper, a new heuristic algorithm is proposed based on harmonic triangle to process the „n‟ jobs in „m‟ machine and it is analysed by using case studies. The results were compared with other heuristics and it shows good results. The author is presently working to find the effectiveness of the proposed heuristic by using well known Tailard bench mark problems which are 120 in numbers. REFERENCES [1] K. R. Baker, Introduction to Sequencing and Scheduling (Wiley, New York, 1974) [2] S.M.Johnson, Optimal two and three machine production scheduling with set up times Included,Naval Research(1954)Log.1, No.1. [3] D. S. Palmer, Sequencing Jobs Through A Multi-Stage Process in the Minimum Total Time- A Quick Method of Obtaining A Near Optimum, Operations Research, 16 (1965) 101-107 [4] H. G. Campbell, R. A. Dudek, and M. L. Smith, A Heuristic Algorithm for the n Job m Machine Sequencing Problem. Management Science 16 (1970) B630-637 [5] D.G.Dannenbring, “An Evaluation of Flow-Shop Sequencing Heuristics”, Management Science 23 (1977), 1174-1182. [6] M. Nawaz, E. Enscore Jr. and I. Ham, “A Heuristic Algorithm for the m-Machine, n- Job Flow-shop Sequencing Problem”, OMEGA, The International Journal of Management Science 11, no 1 (1983) 91-95. http://www.iaeme.com/IJMET/index.asp 288 editor@iaeme.com
A New Heuristic Algorithm to Determine More Than One Sequence in Permutation Flow Shop Scheduling By Using Harmonic Triangle [7] A. Baskar and M.AnthonyXavior, “A Simple Model to obtain more than one sequence having Optimal/ near Optimal Make Span using Dummy Machines”, Advanced Science Letters, Vol. 19, No. 8 (2013), pp.2419-2423.DOI: https://doi.org/10.1166/asl.2013.4881. [8] E. Taillard, “Bench Marks for Basic Scheduling Problems”, European Journal of Operational Research, Vol. 64, No. 2, pp. 278-285 (1993). [9] A.Baskar, “Revisiting the NEH algorithm- the power of job insertion technique for optimizing The makespan in permutation flow shop scheduling”, International Journal of Industrial Engineering Computations,Vol. 7, No. 2 (2016), pp.353-366.DOI: 10.5267/j.ijiec.2015.9.001. [10] EvaValladaa, RubénRuiz and Jose M.Framinan, “New hard benchmark for flowshop Scheduling problemsminimisingmakespan”, European Journal of Operational Research, Vol. 240,No. 3 (2015), pp.666-677. [11] A. Baskar. ”Analysing NEH and a few other similar permutation flow shop scheduling heuristics using Taillard‟s and Vallada‟s benchmarking problems”, International Journal of services and Operations Management, Vol. 30, No. 1 (2018), pp.72-97. [12] R. Panneerselvam, Production and Operations Management , ( Prentice- Hall of India, New Delhi, 2005) http://www.iaeme.com/IJMET/index.asp 289 editor@iaeme.com