Research Article Open Access

Three Algorithms for Flexible Flow-shop Scheduling

Tzung-Pei Hong1, Pei-Ying Huang1, Gwoboa Horng1 and Chan-Lon Wang1
  • 1 ,
American Journal of Applied Sciences
Volume 4 No. 11, 2007, 887-895

DOI: https://doi.org/10.3844/ajassp.2007.887.895

Submitted On: 18 April 2007 Published On: 30 November 2007

How to Cite: Hong, T., Huang, P., Horng, G. & Wang, C. (2007). Three Algorithms for Flexible Flow-shop Scheduling. American Journal of Applied Sciences, 4(11), 887-895. https://doi.org/10.3844/ajassp.2007.887.895

Abstract

Scheduling is an important process widely used in manufacturing, production, management, computer science, and so on. Appropriate scheduling can reduce material handling costs and time. Finding good schedules for given sets of jobs can thus help factory supervisors effectively control job flows and provide solutions for job sequencing. In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, the scheduling problem becomes a flexible flow-shop problem. Flexible flow shops are thus generalization of simple flow shops. In this paper, we propose three algorithms to solve flexible flow-shop problems of more than two machine centers. The first one extends Sriskandarajah and Seth's method by combining both the LPT and the search-and-prune approaches to get a nearly optimal makespan. It is suitable for a medium-sized number of jobs. The second one is an optimal algorithm, entirely using the search-and-prune technique. It can work only when the job number is small. The third one is similar to the first one, except that it uses Petrov's approach (PT) to deal with job sequencing instead of searchand- prune. It can get a polynomial time complexity, thus being more suitable for real applications than the other two. Experiments are also made to compare the three proposed algorithms. A trade-off can thus be achieved between accuracy and time complexity.

  • 1,128 Views
  • 2,791 Downloads
  • 1 Citations

Download

Keywords

  • scheduling
  • flexible flow shop
  • LPT scheduling
  • search
  • PT scheduling