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 originale | Anglais |
|---|---|
| Pages (de - à) | 132-140 |
| Nombre de pages | 9 |
| journal | Computers and Operations Research |
| Volume | 73 |
| Les DOIs | |
| état | Publié - 1 sept. 2016 |
| Modification externe | Oui |
SDG des Nations Unies
Ce résultat contribue à ou aux Objectifs de développement durable suivants
-
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver