Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. FMSscheduling using branchandbound with heuristics
 Institute of Electrical and Electronics Engineers IEEE: 31st IEEE International Conference on Decision and Control '92. Proceedings New York/N.Y., 1992 ISBN: 0780308727 
 Conference on Decision and Control <31, 1992, Tucson/Ariz.> 

 Englisch 
 Konferenzbeitrag 
 Fraunhofer IITB ( IOSB) () 
 branchandbound; control; flexible manufacturing system 
Abstract
In this paper, the generic noncyclic jobshop scheduling problem is solved by an algorithm based on the classical branchandbound method working on a decision tree which represents all possible sequences of operations for the jobshop scheduling problem. The idea of such algorithms is to construct a partial decision tree which contains the optimal solution, but is reduced by cutting of those branches which will only lead to solutions which are worse than the best solution found so far or an upper bound of the cost functional at the optimum which can be estimated from the solutions obtained so far. Unfortunately, for scheduling with respect to minimal tardiness, no efficiently computable bounds are known. To avoid these difficulties we have modified branchandbound algorithms by heuristics based on the following idea: Essential parts of the branchandbound scheme which guarantee that the method will find the optimal schedule are substituted by heuristics in such a way that the resulti ng algorithm will create at least a good schedule within acceptable computation time. The algorithm was tested for a widely accepted benchmark problem and its results are partial better than those of the best known priority rules.