Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/5567
Title: | A fast algorithm to minimize makespan for the two-machine flow-shop problem with release times |
Authors: | Cheng, Jinliang Stephenson, Paul A. Steiner, George McMaster University, Michael G. DeGroote School of Business |
Keywords: | Business;Business |
Publication Date: | Jun-1999 |
Series/Report no.: | Research and working paper series (Michael G. DeGroote School of Business) no. 438 |
Abstract: | <p>We consider the two -machine flow-shop problem with release times where the objec tive is to minimize the makespan. We derive a new dominance order and incorporate it into an efficient branch and bound algorithm which uses an adaptive branching scheme. The algorithm performed very well. It solved within a few seconds 953 of the test prob lems with up to 500 jobs in a large scale computational experiment. For the unsolved problems, the average gap between the best solution found and the optimum was less than 0.53. Experiments also indicate that the speed of the algorithm is largely due to the use of the dominance order which cut solution times roughly in half.</p> |
Description: | <p>26 leaves : ; Includes bibliographical references (leaves 23-24). ; "June, 1999".</p> |
URI: | http://hdl.handle.net/11375/5567 |
Identifier: | dsb/28 1027 4944048 |
Appears in Collections: | DeGroote School of Business Working Paper Series |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 694.24 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.