Minimising makespan in job-shops with deterministic machine availability constraints

Shih Wei Lin, Kuo Ching Ying*

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

6 Scopus citations

Abstract

This paper proposes an effective and efficient multi-temperature simulated annealing (MTSA) algorithm to minimise the makespan of a job-shop under the constraint that machines are not continuously available for processing during the whole scheduling horizon. The proposed MTSA algorithm uses an embedded multi-temperature mechanism to vary the thermal transition probabilities of the simulated annealing algorithm. This mechanism can help prevent the algorithm from becoming trapped in a local minimum and ensures its movement towards a broad region of the search space containing optimal solutions. An effective and robust lower bound is developed for the problem to evaluate the quality of solutions. Extensive computational results show that the proposed MTSA algorithm significantly outperforms the state-of-the-art meta-heuristic algorithms reported in the literature. The proposed algorithm and lower bound can assist further research in the scheduling research field as it is both effective and efficient in handling job-shop scheduling problems with machine availability constraints.

Original languageEnglish
Pages (from-to)4403-4415
Number of pages13
JournalInternational Journal of Production Research
Volume59
Issue number14
DOIs
StatePublished - 2021
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2020 Informa UK Limited, trading as Taylor & Francis Group.

Keywords

  • job-shop
  • machine availability constraints
  • meta-heuristic
  • scheduling

Fingerprint

Dive into the research topics of 'Minimising makespan in job-shops with deterministic machine availability constraints'. Together they form a unique fingerprint.

Cite this