CFP last date
16 December 2024
Call for Paper
January Edition
IJAIS solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 16 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Ordered Frequent Itemsets Matrix Based On Fp-Tree Structure And Apriori Algorithm

Abdulkader M. Al-Badani Abdualmajed A. Al-Khulaidi
Random Articles
Reseach Article

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

by Baskar A, Anthony Xavior M
journal cover thumbnail

International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 6 - Number 4
Year of Publication: 2013
Authors: Baskar A, Anthony Xavior M
10.5120/ijais13-451035

Baskar A, Anthony Xavior M . 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 ( October 2013), 7-15. DOI=10.5120/ijais13-451035

@article{ 10.5120/ijais13-451035,
author = { Baskar A, Anthony Xavior M },
title = { 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 },
issue_date = { October 2013 },
volume = { 6 },
number = { 4 },
month = { October },
year = { 2013 },
issn = { 2249-0868 },
pages = { 7-15 },
numpages = {9},
url = { https://www.ijais.org/archives/volume6/number4/538-1035/ },
doi = { 10.5120/ijais13-451035 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T18:52:30.110350+05:30
%A Baskar A
%A Anthony Xavior M
%T Analyzing a few Heuristic Algorithms Considering Machine Idle Time and Processing Time in Permutation Flow Shop Scheduling Problems
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 6
%N 4
%P 7-15
%D 2013
%I Foundation of Computer Science (FCS), NY, 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.

References
  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
Index Terms

Computer Science
Information Sciences

Keywords

Heuristic Algorithm Flow Shop Scheduling Makespan Benckmark Problems.

Powered by PhDFocusTM