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

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.