Scheduling jobs on parallel machines: A restricted tabu search approach

Chang Ouk Kim, Hyun Joon Shin

Research output: Contribution to journalArticlepeer-review

48 Citations (Scopus)


Many real scheduling problems are often much more complex than problems that are analytically tractable. The main difficulty in obtaining optimal job schedules arises from the existence of sequence dependent setup times among jobs and job release times. In this paper, we present a restricted tabu search algorithm that schedules jobs on parallel machines in order to minimise the maximum lateness of the jobs. The jobs have release times and due dates, and sequence-dependent setup times exist between the jobs. The parallel machines are either identical or non-identical in terms of the processing times of the jobs. The restricted tabu search algorithm employs a restricted search with the elimination of non-effective job moves, for finding the best neighbourhood schedule. The restricted search algorithm reduces search effort significantly while obtaining good quality final schedule. The experimental results show that the proposed algorithm obtains much better solutions more quickly than other heuristic algorithms such as the Rolling Horizon Procedure (RHP) heuristic, the basic tabu search and simulated annealing.

Original languageEnglish
Pages (from-to)278-287
Number of pages10
JournalInternational Journal of Advanced Manufacturing Technology
Issue number3-4
Publication statusPublished - 2003

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Mechanical Engineering
  • Computer Science Applications
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Scheduling jobs on parallel machines: A restricted tabu search approach'. Together they form a unique fingerprint.

Cite this