An algorithm for single machine sequencing with release dates to minimize maximum cost

AbstractThe problem of scheduling jobs on a single machine with release dates, precedence constraints and general cost functions is considered. An algorithm of the branch-and-bound type for minimizing maximum cost is proposed. The algorithm is based on the eliminative properties of a block of jobs. Dominance relations between lower bounds are discussed and some heuristic methods for minimizing maximum cost are analyzed. Computational experiments reveal the high efficiency of the algorithm; it has solved test problems with 300 jobs