Research Article
A New Heuristic Algorithm using Pascalís Triangle to Determine more than one Sequence having Optimal/ near Optimal Make Span in Flow Shop Scheduling Problems
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 39 - Issue 5 |
| Published: February 2012 |
| Authors: Baskar A, Anthony Xavior M |
10.5120/4815-7053
|
Baskar A, Anthony Xavior M . A New Heuristic Algorithm using Pascalís Triangle to Determine more than one Sequence having Optimal/ near Optimal Make Span in Flow Shop Scheduling Problems. International Journal of Computer Applications. 39, 5 (February 2012), 9-15. DOI=10.5120/4815-7053
@article{ 10.5120/4815-7053,
author = { Baskar A,Anthony Xavior M },
title = { A New Heuristic Algorithm using Pascalís Triangle to Determine more than one Sequence having Optimal/ near Optimal Make Span in Flow Shop Scheduling Problems },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 39 },
number = { 5 },
pages = { 9-15 },
doi = { 10.5120/4815-7053 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A Baskar A
%A Anthony Xavior M
%T A New Heuristic Algorithm using Pascalís Triangle to Determine more than one Sequence having Optimal/ near Optimal Make Span in Flow Shop Scheduling Problems%T
%J International Journal of Computer Applications
%V 39
%N 5
%P 9-15
%R 10.5120/4815-7053
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In this paper, an attempt is made to find a sequence having optimal or near optimal make span in a flow shop scheduling of ‘n’ jobs in ‘m’ machines using a newly proposed heuristic algorithm based on Pascal’s Triangle (for nCr) . It is simple and can be easily coded in any high level language to run in a computer for effective and fast computation. Also, the effectiveness of the new Heuristic is analyzed using few case studies in comparison with some of the popular Heuristics like RA Heuristics, Palmer Heuristics, Gupta Heuristics, CDS Heuristics and Johnson’s algorithm.
References
- Johnson, S. M, “Optimal two and three machine production scheduling with set up times included”, Naval Research, Log 1, No. 1 (1954).
- Conway, R. W., Maxwell, W. L. and Miller, L. W. 1967 Theory Of Scheduling Dover Publications INC.
- Baker, K. R. 1974 Introduction to sequencing and scheduling Wiley.
- Palmer, D. S., “Sequencing jobs through a multi stage process in the minimum total time – A quick method for obtaining a near optimum”, Operations Research 16 (1965), 101-107.
- Gupta, J. N. D., “A Functional Heuristic Algorithm for the Flow Shop Scheduling Problems”, Operations Research 22 (1971), 39-47.
- Campbell, H. G., Dudek, R. A. and Smith, M. L.,”A Heuristic Algorithm for the n Job m Machine Sequencing Problem”, Management Science 16 (1970), B630-637.
- Dannenbring, D. G., “An Evaluation of Flow-Shop Sequencing Heuristics”, Management Science 23 (1977), 1174-1182.
- Nawaz, M, Enscore Jr., E and Ham, I, “A Heuristic Algorithm for the m-Machine, n-Job Flow-Shop Sequencing Problems”, OMEGA, The International Journal Of Management Science 11, no.1 (1983), 91-95.
- Ho, J. C. and Chang, Y. I., “A new heuristic for the n-job, m-machine flow shop Problem”, European Journal Of Operations Research 52 (1990), 194-206.
- Quan-Ke-Pan, Ling Wang and Bao-Hua Zhao, “An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with make span criterion”, International Journal of Advanced Manufacturing Technology 38 (2008), 778-786.
- Mohammad Kazem Sayadia, Reza Ramezaniana and Nader Ghaffari-Nazab, “A discrete firefly meta-heuristic with local search for make span minimization in permutation flow shop scheduling problems”, International Journal of Industrial Engineering Computations 1 (2010), 1-10.
- Uday Kumar Chakraborty and Dipak Laha, “An improved Heuristic for permutation flow shop scheduling”, International Journal of Information and communication technology 1 No.1 (2007).
- Dipak Laha and Uday Kumar Chakraborty, “An efficient hybrid heuristic for make span minimization in permutation flow shop scheduling”, International Journal of Advanced Manufacturing Technology 44 (2009), 559-569.
- Dipak Laha and Uday Kumar Chakraborty, “A constructive heuristic for minimizing make span in no-wait flow shop scheduling”, International Journal of Advanced Manufacturing Technology 41 (2009), 97-109.
- Dipak Laha and Arindam Chakravorty, “A new heuristic for minimizing total completion time objective in permutation flow shop scheduling”, International Journal of Advanced Manufacturing Technology DOI 10.1007/s00170-010-2895-9.
- Ravindran, D, Noorul Hag, A, Selva Kumar, S. J. and Siva Raman, R, “Flow shop scheduling with multi objective of minimizing make span and total flow time”, International Journal of Advanced Manufacturing Technology 25 (2005), 1007-1012.
- Allaverdi, A and Al-Anzi, F. S., “The two stage assembly flow shop scheduling problem with bi-criteria of make span and mean completion time”, International Journal of Advanced Manufacturing Technology 37 (2008), 166-177.
- Ming-Cheng Lo, Jen-Shing Chen and Yong-Fo Chang, “Minimizing make span and mean flow time in Two-Versatile machine Flow Shop with alternative operations”, Information Technology Journal 9(2) (2010), 257-265.
- Mohammad Mirabi, “Ant colony optimization technique for the sequence-dependent for the flow shop scheduling problem”, International Journal of Advanced Manufacturing Technology DOI 10.1007/s00170-010-3037-0.
- Panneer Selvam, R. 2005 Production and Operations Management Prentice Hall of India.
Index Terms
Keywords