Fast algorithms to minimize the makespan or maximum lateness in the two-machine flow shop with release times
✍ Scribed by Jinliang Cheng; George Steiner; Paul Stephenson
- Publisher
- Springer US
- Year
- 2002
- Tongue
- English
- Weight
- 186 KB
- Volume
- 5
- Category
- Article
- ISSN
- 1094-6136
- DOI
- 10.1002/jos.94
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the two-machine ow-shop problem with release times where the objective is to minimize either the makespan or the maximum lateness. We present a uniÿed treatment of various sequenceinterchange operators and derive powerful new dominance orders, which are incorporated into branchand-bound algorithms. The dominance orders produced substantial savings in the average solution time, making the algorithms very fast. They solved, within a few seconds, more than 97 per cent of the test problems with up to 500 jobs for both objectives. For the unsolved problems, the average gap from the optimum was less than 0.5 per cent.