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

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

0.00 Avg rating0 Votes
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: , ,
Keywords: manufacturing industries, programming: branch and bound, combinatorial optimization, programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.