Show simple item record

dc.contributor.authorSteinhofel, K.
dc.contributor.authorAlbrecht, A.
dc.contributor.authorWong, C.K.
dc.identifier.citationSteinhofel , K , Albrecht , A & Wong , C K 2003 , ' An Experimental Analysis of Local Minima to Improve Neighbourhood Search ' , Computers and Operations Research , vol. 30 , no. 14 , pp. 2157-2173 .
dc.identifier.otherPURE: 91520
dc.identifier.otherPURE UUID: c3c36ed5-905f-449c-a777-d9f1a35ec86c
dc.identifier.otherdspace: 2299/4300
dc.identifier.otherScopus: 0041887248
dc.descriptionOriginal article can be found at: Copyright Elsevier Ltd. DOI: 10.1016/S0305-0548(02)00128-4 [Full text of this article is not available in the UHRA]
dc.description.abstractThe paper reports the results from a number of experiments on local search algorithms applied to job shop scheduling problems. The main aim was to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e. the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.en
dc.relation.ispartofComputers and Operations Research
dc.titleAn Experimental Analysis of Local Minima to Improve Neighbourhood Searchen
dc.contributor.institutionSchool of Computer Science
dc.contributor.institutionScience & Technology Research Institute
dc.description.statusPeer reviewed
rioxxterms.typeJournal Article/Review

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record