Abstract
In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints.
Original language | English (US) |
---|---|
Pages (from-to) | 1091-1102 |
Number of pages | 12 |
Journal | INFORMS Journal on Computing |
Volume | 33 |
Issue number | 3 |
DOIs | |
State | Published - Jun 2021 |
Keywords
- Bound
- Branch
- Combinatorial optimization
- One-machine scheduling
ASJC Scopus subject areas
- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research