LOCAL SEARCH HEURISTICS FOR SINGLE-MACHINE SCHEDULING WITH BATCHING TO MINIMIZE THE NUMBER OF LATE JOBS

Local search heuristics are developed for a problem of scheduling jobs on a single machine. Jobs are partitioned into families, and a set-up time is necessary when there is a switch in processing jobs from one family to jobs of another family. The objective is to minimize the num ber of late jobs. Four alternative local search methods are proposed: multi-start descent, simulated annealing, tabu search and a genetic al gorithm. The performance of these heuristics is evaluated on a large s et of test problems. The best results are obtained with the genetic al gorithm; multi-start descent also performs quite well.