### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 163-175 |

Number of pages | 13 |

Journal | Journal of Scheduling |

Volume | 12 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1 2009 |

### Keywords

- Branch and bound algorithms
- Dynamic programming
- Scheduling theory and algorithms

### ASJC Scopus subject areas

- Software
- Engineering(all)
- Management Science and Operations Research
- Artificial Intelligence

## Fingerprint Dive into the research topics of 'A branch, bound, and remember algorithm for the 1|r <sub>i</sub> |σt <sub>i</sub> scheduling problem'. Together they form a unique fingerprint.

## Cite this

_{i}|σt

_{i}scheduling problem.

*Journal of Scheduling*,

*12*(2), 163-175. https://doi.org/10.1007/s10951-008-0087-3