Skip to main navigation Skip to search Skip to main content

A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

  • Universidad EAFIT
  • Universidad de la Sabana

Research output: Contribution to journal › Journal Article › peer-review

37 Citations (Scopus)

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 languageEnglish
Pages (from-to)132-140
Number of pages9
JournalComputers and Operations Research
Volume73
DOIs
Publication statusPublished - 1 Sept 2016
Externally publishedYes

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

  1. SDG 9 - Industry, Innovation, and Infrastructure
    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