Tuning of Tabu Search Method for Optimal Scheduling Problems

Tabu search is a stochastic optimization method which is appropriate for large nonconvex optimization problems.  While it has been applied to many problems including some in the area of scheduling, there have previously been no systematic studies on the selection of algorithm parameters.  Tabu search has many such parameters, including the length of the Tabu list and the number of instances of the algorithm to run simultaneously.  These parameters are functions of problem size and structure, and currently are set via a trial-and-error method.  This work seeks to develop simple heuristics which allow the parameters for Tabu search to be set automatically.  The heuristics also must be varied based on the serial or parallel computer architecture available.  These heuristcs are evaluated for the solution of a set of batch scheduling problems, including the resource-constrained, continuous-time scheduling problem of Jain and Grossmann [1]..  Results are provided which compare the novel tuning method with the use of fixed values for Tabu search parameters, and computation times are compared to those obtained with deterministic methods as well.  The tuning of a parallel Tabu search implementation was also evaluated, in terms of both speedup and robustness on the same set of test problems. 

[1]  Jain, V. and I.E. Grossmann, Resource-Constrained Scheduling of Tests in New Product Development, Ind. Eng. Chem. Res. 1999, 38, 3013-3026.