A performance comparison of PSO and GA in scheduling hybrid flow-shops with multiprocessor tasks

ABSTRACT

Applications in industry and computing require a proper scheduling of tasks to achieve good performance. The algorithms presented in this paper tackles task scheduling problem in a multi layer multiprocessor environment. Using the scheduling terminology, problem is defined as multiprocessor task scheduling in hybrid flow-shops. This paper presents a particle swarm optimization (PSO) algorithm for the solution. In order to improve the performance of PSO, hybrid techniques were also employed. The performance results, compared with other well known meta-heuristics from the literature, are reported. Results show that PSO and hybrid methods have merits in solving multiprocessor task scheduling in hybrid flow-shop environment.

REFERENCES

• 1: Caraffa, V., Ianes, S., Bagchi, T. P., and Sriskandarajah, C. Minimizing Make-Span in Blocking Flow-Shop Using Genetic Algorithms, International Journal of Production Economics, 70( 2001), 101--115.
• 2: Chan, J., and Lee, C. Y. General Multiprocessor Task Scheduling, Naval Research Logistics, 46 (1999), 57--74.
• 3: Drozdowski, M. Scheduling Multiprocessor Tasks - An Overview, European Journal of Operational Research, 94 (1996), 215--230.
• 4: Ercan, M. F., and Fung, Y. F. The Design and Evaluation of a Multiprocessor System for Computer Vision, Microprocessors and Microsystems, 24 (2000), 365--377.
• 5: Gupta, J. N. D, Hariri, A. M. A., and Potts, C. N. Schedules for a Two-stage Hybrid Flow-shop with Parallel Machines at First Stage, Ann. Oper. Res. Soc., 69 (1997), 171--191.
• 6: Kennedy, J., and Eberhart, R. Particle Swarm Optimization, Proceedings of IEEE Int. Conf. on Neural Network, 1995, 1942--1948.
• 7: Henryk Krawczyk, An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems, IEEE Transactions on Computers, v.34 n.9, p.869-872, September 1985 [doi>10.1109/TC.1985.1676647]
• 8: Lee, C. Y., and Cai, X. Scheduling One and Two-processors Tasks on Two Parallel Processors, IIE Transactions, 31 (1999), 445--455.
• 9: Richard Linn , Wei Zhang, Hybrid flow shop scheduling: a survey, Computers and Industrial Engineering, v.37 n.1-2, p.57-61, Oct. 1999 [doi>10.1016/S0360-8352(99)00023-6]
• 10: Oǧuz, C., Ercan, M. F., Cheng, T. C. E., and Fung, Y. F. Heuristic Algorithms for Multiprocessor Task Scheduling in a Two Stage Hybrid Flow Shop, European Journal of Operations Research, 149 (2003) 390--403.
• 11: Oǧuz, C., Zinder, Y., Do., V., Janiak, A., and Lichtenstein, M. Hybrid Flow-Shop Scheduling Problems with Multiprocessor Task Systems, European Journal of Operations Research, 152 (2004) 115--131.
• 12: Ceyda Oĝuz , M. Fikret Ercan, A Genetic Algorithm for Hybrid Flow-shop Scheduling with Multiprocessor Tasks, Journal of Scheduling, v.8 n.4, p.323-351, July 2005 [doi>10.1007/s10951-005-1640-y]
• 13: Ying, K. C., and Lin, S. W. Multiprocessor Task Scheduling in Multistage Hybrid Flow-Shops: an Ant Colony System Approach, International Journal of Production Research, 44 (2006), 3161--3177.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Experimentation

Keywords:
flow shops, hybrid particle swarm optimization, multiprocessor task scheduling