An approximate/exact objective based search technique for solving general scheduling problems.

In this paper, we analyze single machine scheduling problems under the following minimization objectives: the maximum completion time (makespan), the total completion time and the maximum lateness, including fundamental practical aspects, which often occur in industrial or manufacturing reality: release dates, due dates, setup times, precedence constraints, deterioration (aging) of machines, as well as maintenance activities. To solve the problems, we propose an efficient representation of a solution and a fast neighborhood search technique, which calculates an approximation of criterion values in a constant time per solution in a neighborhood. On this basis, a novel approximate/exact search technique, using exact as well as approximate criterion values during search process, is introduced and used to develop efficient metaheuristic algorithms dedicated to the considered problems. Their efficiency is verified during computational experiments. [ABSTRACT FROM AUTHOR]