Passer à la navigation principale Passer à la recherche Passer au contenu principal

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

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

37 Citations (Scopus)

Résumé

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.

langue originaleAnglais
Pages (de - à)132-140
Nombre de pages9
journalComputers and Operations Research
Volume73
Les DOIs
étatPublié - 1 sept. 2016
Modification externeOui

SDG des Nations Unies

Ce résultat contribue à ou aux Objectifs de développement durable suivants

  1. SDG 9 – Industrie, innovation et infrastructure
    SDG 9 – Industrie, innovation et infrastructure

Empreinte digitale

Voici les principaux termes ou expressions associés à « A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource