Tabu Search for a Class of Single-Machine Scheduling Problems

In this paper we develop a tabu search-based solution procedure designed speci"cally for a certain class of single-machine scheduling problems with a non-regular performance measure. The performance of the developed algorithm is tested for solving the variance minimization problem. Problems from the literature are used to test the performance of the algorithm. This algorithm can be used for solving other problems such as minimizing completion time deviation from a common due date. Scope and purpose Scheduling problems with non-regular performance measures has gained a great importance in modern manufacturing systems. These problems are found to be hard to solve and analyze. The purpose of this paper is to present a tabu search approach for solving a certain class of single-machine scheduling problems with non-regular performance measure. Minimizing the variance of completion times and the total deviation from a common due date are two examples of such problems. The proposed approach is found to perform better than the simulated annealing approach for the variance minimization problem. � 2001 Elsevier Science Ltd. All rights reserved. Keywords: Tabu search; Scheduling; Variance minimization; V-shaped schedule