Local search algorithms for a single-machine scheduling problem with positive and negative time-lags

Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced by Roy (C.R. Acad. Sci., 1959, T.248) in connection with the Metra Potential Method. Although very powerful, these relations have been considered only seldom in the literatur e since already for a single-machine problem with positive and negative tim e-lags the problem of finding a feasible solution is NP-complete. In this p aper a local search approach for a single-machine scheduling problem with p ositive and negative time-lags and the objective to minimize the makespan i s presented. Since the existence of a feasible initial solution for startin g the search can not be guaranteed, infeasible solutions are incorporated i nto the search process. Computational results based on instances resulting from shop problems are reported. (C) 2001 Elsevier Science B.V. All rights reserved.