Article ID: | iaor20118731 |
Volume: | 39 |
Issue: | 5 |
Start Page Number: | 939 |
End Page Number: | 951 |
Publication Date: | May 2012 |
Journal: | Computers and Operations Research |
Authors: | Jiang Zhibin, Li Na, Yao Shiqing |
Keywords: | manufacturing industries, programming: branch and bound, combinatorial optimization, programming: dynamic |
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.