Trimming-the-state-space mechanism embedded branch-and-bound algorithm for two-parallel machines scheduling with availability constraints

Anh H.G. Nguyen, Gwo Ji Sheen

Research output: Contribution to journalArticlepeer-review

Abstract

In this research, a trimming-the-state-space mechanism is embedded into the branch-and-bound algorithm to improve the performance of the pure branch-and-bound algorithm in finding a near-optimal solution with a pre-specified error bound. We propose general guidelines for trimming out nodes in the branching process while elimination criteria and bounding schemes are still utilized to eliminate nodes. As to the performance evaluation, we apply the proposed algorithm to a two-parallel machines scheduling problem with machine availability constraints. Computational results indicate that the proposed approximation algorithm performs very efficiently compared to the pure branch-and-bound algorithm in terms of run time and problem sizes. The error bound of the proposed algorithm is also demonstrated to be within the specified ε-value. Besides, it shows that our algorithm outperforms an existing heuristic from the literature in terms of solution quality.

Original languageEnglish
Article number110002
JournalComputers and Industrial Engineering
Volume190
DOIs
StatePublished - Apr 2024

Keywords

  • Approximation algorithm
  • Brand-and-Bound algorithm
  • Machine availability constraints
  • Parallel-machine scheduling problem
  • Trimming-the-state-space approach

Fingerprint

Dive into the research topics of 'Trimming-the-state-space mechanism embedded branch-and-bound algorithm for two-parallel machines scheduling with availability constraints'. Together they form a unique fingerprint.

Cite this