Single machine scheduling with major and minor setup times: A tabu search approach

The paper deals with a single machine scheduling problem in which jobs are grouped into families that require major setup times, and where jobs within families require for processing minor setup times. The former are sequence dependent and the latter have special triangular structure. The problem is to find a partition of families into batches, sequences of jobs in particular batches and a sequence of batches which minimize a general regular cost function. The tabu search algorithm for finding near-optimal schedules is proposed and results of computational experiments are presented.