Abstract
This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost.
| Original language | English |
|---|---|
| Pages (from-to) | 132-140 |
| Number of pages | 9 |
| Journal | Computers and Operations Research |
| Volume | 73 |
| DOIs | |
| Publication status | Published - 1 Sept 2016 |
| Externally published | Yes |
UN SDGs
This output contributes to the following UN Sustainable Development Goals (SDGs)
-
SDG 9 Industry, Innovation, and Infrastructure
Keywords
- Beam search
- Makespan
- Release dates
- Sequence-dependent setup times
- Single machine scheduling
ASJC Scopus subject areas
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research
Fingerprint
Dive into the research topics of 'A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver