A branch, bound, and remember algorithm for the 1|r
i
|∑t
i
scheduling problem |
| |
Authors: | Gio K Kao Edward C Sewell Sheldon H Jacobson |
| |
Affiliation: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 201 North Goodwin Ave. (MC-258), Urbana, IL 61801-2302, USA;(2) Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, IL 62026, USA |
| |
Abstract: | This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm,
which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r
i
|∑t
i
scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total
tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based
dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1|r
i
|∑t
i
scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy
outperforms the best known algorithms reported in the literature. |
| |
Keywords: | Branch and bound algorithms Scheduling theory and algorithms Dynamic programming |
本文献已被 SpringerLink 等数据库收录! |
|