Skip to main navigation Skip to search Skip to main content

Machine scheduling with sequence-dependent setup times using a randomized search heuristic

  • Universidad de la Sabana
  • Universidad del Norte

Research output: Contribution to Book/Report types › Contribution to conference proceedings › peer-review

8 Citations (Scopus)

Abstract

This paper considers the problem of scheduling a set of jobs on both asingle machine and identical parallel machines with the objective of minimizingthe makespan or maximum completion time of all jobs. Jobs are subject to releasedates and there are sequence-dependent setup times. Since this problem is knownto be strongly NP-hard even for the single machine case, this paper proposes aheuristic algorithm to solve it. The algorithm uses a strategy of randomgeneration of various execution sequences, and then selects the best of suchschedules. Experiments are performed using random-generated data. Results showthat the heuristic performs very well compared against the optimal solution, andrequiring short computational time.

Original languageEnglish
Title of host publication2009 International Conference on Computers and Industrial Engineering, CIE 2009
PublisherIEEE Computer Society
Pages28-33
Number of pages6
ISBN (Print)9781424441365
Publication statusPublished - 2009
Externally publishedYes
Event2009 International Conference on Computers and Industrial Engineering, CIE 2009 - Troyes, France
Duration: 6 Jul 2009 → 9 Jul 2009

Publication series

Name2009 International Conference on Computers and Industrial Engineering, CIE 2009

Conference

Conference2009 International Conference on Computers and Industrial Engineering, CIE 2009
Country/TerritoryFrance
CityTroyes
Period6/07/09 → 9/07/09

Keywords

  • Heuristic
  • Parallel machines
  • Scheduling
  • Setup times
  • Single machine

ASJC Scopus subject areas

  • Control and Systems Engineering
  • General Computer Science
  • Electrical and Electronic Engineering
  • Industrial and Manufacturing Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Machine scheduling with sequence-dependent setup times using a randomized search heuristic'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this