## Abstract

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be NP-hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.

Original language | English |
---|---|

Pages (from-to) | 459-469 |

Number of pages | 11 |

Journal | Omega |

Volume | 31 |

Issue number | 6 |

DOIs | |

State | Published - 1 Dec 2003 |

## Keywords

- Branch-and-bound algorithm
- Heuristic algorithm
- Linear deterioration
- Maximum lateness
- Operations scheduling