Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop

C. Oǧuz, M. Fikret Ercan, Edwin Tai Chiu Cheng, Y. F. Fung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

79 Citations (Scopus)

Abstract

The aim of this paper is to propose heuristic algorithms for a two-stage flow-shop scheduling problem with multiprocessor tasks to minimize the makespan. The heuristic algorithms are constructive in nature. They schedule the tasks one at a time from a given sequence. The rules considered for sequencing the tasks are based on simple priority rules from the literature. Some lower bounds for the problem are also derived to be used in the performance analysis of the heuristic algorithms. Next, the average performance of the proposed heuristic algorithms is analyzed by a computational experiment using randomly generated problem instances. The results suggest that these heuristic algorithms are both efficient and effective. The paper concludes with a discussion of the insights obtained from the experimental analysis about this type of scheduling problems.
Original languageEnglish
Pages (from-to)390-403
Number of pages14
JournalEuropean Journal of Operational Research
Volume149
Issue number2
DOIs
Publication statusPublished - 1 Sep 2003

Keywords

  • Flow-shop
  • Heuristics
  • Makespan, Multiprocessor task scheduling
  • Performance evaluation

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this