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

Share/Save/Bookmark

Hurink, J.L. and Keuchel, J. (2001) Local search algorithms for a single-machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics, 112 (1-3). pp. 179-197. ISSN 0166-218X

[img] PDF
Restricted to UT campus only
: Request a copy
138kB
Abstract: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 literature since already for a single-machine problem with positive and negative time-lags the problem of finding 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 can not be guaranteed, infeasible solutions are incorporated into the search process. Computational results based on instances resulting from shop problems are reported.
Item Type:Article
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/63582
Official URL:http://dx.doi.org/10.1016/S0166-218X(00)00315-2
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page