A bicriteria scheduling with sequence-dependent setup times

Abstract

In this paper a bicriteria scheduling problem with sequence-dependent setup times on a single machine is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. An integer programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 12 jobs. For solving problems containing large number of jobs a special heuristic algorithm is proposed. Besides the proposed heuristic algorithm tabu search based heuristic is also used for large jobs problems. To improve the performance of tabu search method the result of the proposed heuristic algorithm is taken as an initial solution of tabu search method. According to computational results both heuristic algorithms are effective in finding problem solutions with up to 1000 jobs. According to the best of our knowledge, no works exists on the minimization of the weighted sum of total completion time and total tardiness with sequence-dependent setup times. (c) 2005 Elsevier Inc. All rights reserved.