Back to Search Start Over

Neighborhood search algorithm for one-machine scheduling problem with time lags

Authors :
Zhao Ruiguo
Li Jiejia
Source :
2009 Chinese Control and Decision Conference.
Publication Year :
2009
Publisher :
IEEE, 2009.

Abstract

The one-machine scheduling problem with time lags while minimizing the completion time is NP-hard. The problem typically arises in a manufacturing where the next job has to be carried out in a specific time window after the completion of the immediately proceeding job. Scheduling the jobs is to find a shortest path that passes all the nodes and meets all precedence constraints and time lags constraints on AON (Activity-On-Node) net. A nonlinear mathematic optimization model is established based on AON net. A neighborhood search algorithm is proposed to convert the nonlinear model into a linear programming model that could be solved by standard software. Computational results prove that the proposed neighborhood search algorithm is effective.

Details

Database :
OpenAIRE
Journal :
2009 Chinese Control and Decision Conference
Accession number :
edsair.doi...........d8754099dea5c9a16c49838dab618763
Full Text :
https://doi.org/10.1109/ccdc.2009.5191609