A tabu search algorithm for scheduling a single robot in a job-shop environment

Johann L. Hurink, Sigrid Knust

Research output: Contribution to journalArticleAcademicpeer-review

52 Citations (Scopus)
27 Downloads (Pure)

Abstract

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the travelling-salesman problem with time windows, where additionally generalized precedence constraints have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all travelling and waiting times is minimized. We present a local search algorithm for this problem where an appropriate neighborhood structure is defined using problem-specific properties. In order to make the search process more efficient, we apply some techniques which accelerate the evaluation of the solutions in the proposed neighbourhood considerably. Computational results are presented for test data arising from job-shop instances with a single transport robot.
Original languageEnglish
Pages (from-to)181-203
Number of pages23
JournalDiscrete applied mathematics
Volume119
Issue number1-2
DOIs
Publication statusPublished - 15 Jun 2002

Keywords

  • MSC-90B35
  • Traveling salesman problem with time windows
  • Tabu search
  • Time-lags
  • Scheduling

Fingerprint

Dive into the research topics of 'A tabu search algorithm for scheduling a single robot in a job-shop environment'. Together they form a unique fingerprint.

Cite this