Local Search Algorithms for Multiobjective Scheduling Problem

This paper presents local search algorithms for finding approximation solutions of the multiobjective scheduling problem within the single machine context, where the problem is the sum of the three objectives total completion time, maximum tardiness and maximum late work. Late work criterion estimates the quality of a schedule based on durations of late parts of jobs. Local search algorithms descent method (DM), simulated annealing (SA) and genetic algorithm (GA) are implemented. Based on results of computational experiments, conclusions are formulated on the efficiency of the local search algorithms.