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

Johann L. Hurink, J. Keuchel

Research output: Book/ReportReportProfessional

214 Downloads (Pure)

Abstract

Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced in connection with the Metra potential method. Although very powerful, these relations have been considered only seldom in the literature since already for a single machine problem with positive and negative time-lags the problem of finding a feasible solution is ${\cal NP}$-complete. In this paper a local search approach for a single-machine scheduling problem with positive and negative time-lags and the objective to minimize the makespan is presented. Since the existence of a feasible initial solution for starting the search cannot be guaranteed, unfeasible solutions are incorporated into the search process. Computational results based on instances resulting from shop problems are reported.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages24
ISBN (Print)0169-2690
Publication statusPublished - 1998

Publication series

NameMemorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1440
PublisherUniversiteit Twente
No.1440

Keywords

  • EWI-3260
  • METIS-141270
  • IR-30629
  • MSC-90B35

Cite this