Enhanced Branch-and-Bound Framework for a Class of Sequencing Problems

Zizhen Zhang, Luyao Teng, Mengchu Zhou, Jiahai Wang, Hua Wang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In this paper, we propose an enhanced branch-and-bound (BB) framework for a class of sequencing problems, which aim to find a permutation of all involved elements to minimize a given objective function. We require that the sequencing problems satisfy three conditions: 1) incrementally computable; 2) monotonic; and 3) overlapping subproblems. Our enhanced BB framework is built on the classical BB process by introducing two techniques, i.e., dominance rules and caching search states. Following the enhanced BB framework, we conduct empirical studies on three typical and challenging sequencing problems, i.e., quadratic traveling salesman problem, traveling repairman problem, and talent scheduling problem. The computational results demonstrate the effectiveness of our enhanced BB framework when compared to classical BB and some exact approaches, such as dynamic programming and constraint programming. Additional experiments are carried out to analyze different configurations of the algorithm.

Original languageEnglish (US)
Article number8726096
Pages (from-to)2726-2736
Number of pages11
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume51
Issue number5
DOIs
StatePublished - May 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Branch-and-bound (B&B)
  • caching states
  • dominance rules
  • dynamic programming (DP)
  • talent scheduling problem
  • traveling salesman/repairman problem

Fingerprint

Dive into the research topics of 'Enhanced Branch-and-Bound Framework for a Class of Sequencing Problems'. Together they form a unique fingerprint.

Cite this