Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10348031 | Computers & Operations Research | 2012 | 13 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Shiqing Yao, Zhibin Jiang, Na Li,