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