Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

November Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the November 2021 Edition of the journal. The last date of research paper submission is October 15, 2021.

Analyzing a few Heuristic Algorithms Considering Machine Idle Time and Processing Time in Permutation Flow Shop Scheduling Problems

Baskar A, Anthony Xavior M Published in Operational Research

International Journal of Applied Information Systems
Year of Publication: 2013
© 2012 by IJAIS Journal
10.5120/ijais13-451035
Download full text
  1. Baskar A and Anthony Xavior M. Article: Analyzing a few Heuristic Algorithms Considering Machine Idle Time and Processing Time in Permutation Flow Shop Scheduling Problems. International Journal of Applied Information Systems 6(4):7-15, October 2013. BibTeX

    @article{key:article,
    	author = "Baskar A and Anthony Xavior M",
    	title = "Article: Analyzing a few Heuristic Algorithms Considering Machine Idle Time and Processing Time in Permutation Flow Shop Scheduling Problems",
    	journal = "International Journal of Applied Information Systems",
    	year = 2013,
    	volume = 6,
    	number = 4,
    	pages = "7-15",
    	month = "October",
    	note = "Published by Foundation of Computer Science, New York, USA"
    }
    

Abstract

Flow Shop Scheduling has been an interesting field of research for over six decades. They are easy to formulate, yet difficult to solve. In a shop, there are 'm' machines arranged in series to process a set of 'n' jobs having different processing times. Each job has to pass through each machine, in order. The problem is to find a sequence of jobs to be processed in all the machines, so that a given performance parameter is optimized. The total number of schedules is (n!)m. If the order of machines is not to be changed, the problem is simplified, and the overall number of solutions is reduced to n!. This problem is referred to a permutation flow shop scheduling problem, or PFSP in short. Starting from two machines, 'n' jobs, various Heuristics have been proposed over the years. After the invention of meta heuristics and evolutionary algorithms, and increased computational capabilities available today, finding optimal/ near optimal solutions become comparatively easier. In this paper, a few heuristic algorithms have been analyzed for makespan criterion considering machine idle time and processing time, by comparing the results with the well known CDS algorithm. Benchmark problems proposed by Taillard and Ruben Ruiz are used for the performance analysis.

Reference

  1. Rinnooy Kan, A. H. G. 1976. Machine Scheduling Problems: Classification, Complexity, and Computations (The Hague: Martinus Nijhoff).
  2. Baker, K. R. 1974. Introduction to Sequencing and Scheduling. John Wiley & Sons, New York.
  3. Johnson, S. M. 1954. "Optimal two- and three-stage production schedules with setup times included", Naval Research Logistics Quarterly, vol. 1, pp. 61-68.
  4. Palmer, D. S. 1965. "Sequencing jobs through a multi-stage process in the minimum total time - a quick method of obtaining a near optimum", Operational Research Quarterly, vol. 16, No. 1, pp. 101-107.
  5. Camperll, H. G. , Campbell, Dudek, R. A. , and Smith, M. L. 1970. "A heuristic algorithm for the n job, m machine sequencing problem", Management Science, vol. 16, No. 10, pp. B630–B637.
  6. Dannenbring, D. G. 1977. "An evaluation of flow shop sequencing heuristics", Management Science, vol. 23, No. 11, pp. 1174–1182.
  7. Nawaz, M, Enscore, Jr, E. E. , and Ham, I. (1983). "A heuristic algorithm for the m- machine, n-job flow-shop sequencing problem", OMEGA, The International Journal of Management Science, vol. 11, No. 1, pp. 91–95.
  8. Turner, S. and Booth, D. 1977. "Comparison of heuristics for flow shop sequencing", OMEGA, The International Journal of Management Science, vol. 15, No. 1, pp. 75-78.
  9. Taillard, E. 1990. "Some efficient heuristic methods for the flow shop sequencing problem", European Journal of Operational Research, vol. 47, pp. 67–74.
  10. Ruiz, R. and Maroto, C. 2005. "A comprehensive review and evaluation of permutation flowshop heuristics", European Journal of Operational Research, vol. 165, pp. 479–494.
  11. Framinan, J. M. , Leisten, R. , and Rajendran, C. 2003. "Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem", International Journal of Production Research, vol. 41, No. 1, pp. 121–148.
  12. Taillard, E. 1993. "Benchmarks for basic scheduling problems", European Journal of Operational Research, vol. 64, pp. 278–285.
  13. Ruben Ruiz problems available at http://soa. iti. es

Keywords

Heuristic Algorithm, Flow Shop Scheduling, Makespan, Benckmark Problems.