Bi-direction branch and bound method to solve the single machine total weighted completion time problem with job release times

摘要

This paper considers the problem of scheduling n jobs on a single machine to minimize the total weighted completion time. Each job has a release time, a processing time and a weight. For the problem, we present a bi-direction branching scheme based on branch and bound method, called bi-direction branch and bound (BDBAD), which incorporates forward-driven and backward-driven schemes and emphasizes the use of bi-direction branching in determining lower bounds. We offered an example to illustrate the BDBAD method, and compare it with the ILOG OPL version 3.7 which is a well-known optimization tool to obtain optimal solutions. The results showed that the proposed BDBAD method can significantly reduce the total number of branching nodes compared with the nodes branched by ILOG OPL.