Title: A tabu search algorithm for no-wait job shop scheduling problem

Authors: Ghafour Ahani; Mostafa Asyabani

Addresses: Department of Mathematics, College of Science, Payam-e-Noor University, Postal Code: 6681989396, Shahrak-e-Daneshgah, Saghez, Kurdistan, Iran ' Department of Mathematics, College of Science, Payam-e-Noor University, Postal Code: 6681989396, Shahrak-e-Daneshgah, Saghez, Kurdistan, Iran

Abstract: In this paper, we consider no-wait job shop scheduling problem with makespan objective. In the no-wait problem two consecutive operations in each job must be processed without any interruption. No-wait job shop problem is strongly NP-hard. Mascis and Pacciarelli proposed an algorithm for no-wait job shop problem that produces good quality solution for benchmark problems but it mostly failed in finding a feasible solution. Therefore, we introduce a new neighbourhood structure in our tabu search to resolve this problem.

Keywords: no-wait scheduling; job shop scheduling; tabu search; alternative graph; makespan.

DOI: 10.1504/IJOR.2014.058954

International Journal of Operational Research, 2014 Vol.19 No.2, pp.246 - 258

Received: 02 May 2012
Accepted: 08 Oct 2012

Published online: 25 Jan 2014 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article