A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals

Shiqing Yao, Zhibin Jiang, Na Li

Research output: Contribution to journalArticleResearchpeer-review

30 Citations (Scopus)


In this paper, we consider a single batch machine scheduling problem with incompatible job families and dynamic job arrivals. The objective is to minimize the total completion time. This problem is known to be strongly NP-hard. We present several dominance properties and two types of lower bounds, which are incorporated to construct a basic branch and bound algorithm. Furthermore, according to the characteristics of dynamic job arrivals, a decomposed branch and bound algorithm is proposed to improve the efficiency. The proposed algorithms are tested on a large set of randomly generated problem instances.

Original languageEnglish
Pages (from-to)939-951
Number of pages13
JournalComputers and Operations Research
Issue number5
Publication statusPublished - May 2012
Externally publishedYes

Cite this