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

82 Citations (Scopus)


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
Issue number2
Publication statusPublished - 1 Sept 2003


  • 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


Dive into the research topics of 'Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop'. Together they form a unique fingerprint.

Cite this