Heuristikker for openshop og flowshop

Susanne Rasmussen

AbstractThis note describes a number of different methods, which alone or combined can be used to solve the open-shop and flow-shop problems. The methods are presented and examples solved in order to compare the degree of difficulty in implementation, the accuracy of the solutions and the needed computational time for the different methods. In most cases the computational time needed in the programs developed, could be reduced by a computer-wizard, but since everything was developed by me (an average programmer), the relative times should be accurate enough to show if one method is better or worse than another. Further more the fact that an average programmer developed the programs should bring any implementational problems in the methods to light. The methods implemented are H1, Simulated Annealing, HFC and H1 adapted to flowshopproblems. The algorithms H2, Branch and Bound and Tabu search are examined but not implemented.

HFC is found to be the best of those algorithms implemented for solving large flowshopproblems and H1 the best for solving large openshopproblems. This was in both cases due to the speed of the algorithms, the relative accuracy and the ease of implementing them.
Keywordspen-shop, flow-shop, simulated annealing, HFC, H1, H2
TypeMaster's thesis [Academic thesis]
Year2001
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-EKS-2001-23
Electronic version(s)[pdf]
BibTeX data [bibtex]
IMM Group(s)Operations Research