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

Share/Save/Bookmark

Hurink, J.L. and Keuchel, J. (1998) Local search algorithms for a single-machine scheduling problem with positive and negative time-lags. [Report]

[img]
Preview
PDF
179Kb
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 nding a feasible
solution is 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, infeasible solutions are incorporated
into the search process. Computational results based on instances
resulting from shop problems are reported.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/30629
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 141270