<p>This paper focuses on a single-machine problem that take into account delivery times and deteriorating jobs. Specifically, the processing time of a job is a simple linear function of its start time, and each job has a delivery time. The objective is to minimize the maximum delivery completion time. Given that this problem is NP-hard, several dominance properties, upper bounds, and lower bounds are derived, then a branch-and-bound algorithm is designed based on these properties. Additionally, a mixed integer programming model and a number of heuristic algorithms (including the NEH algorithm, Tabu Search (TS), and Simulated Annealing (SA)) are proposed. The performance of the branch-and-bound algorithm and heuristic algorithms is compared through experimental results.</p>