کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5127575 | 1489054 | 2017 | 12 صفحه PDF | دانلود رایگان |
- B&B algorithm with release-date-based branching rule for small-scale problems.
- DDE algorithm with multi-point insertion scheme for moderate-scale problems.
- A lower bound with performance guarantee for large-scale problems.
- Worst-case analysis for the SPTA-based heuristic under the consistency condition.
In a dynamic flow shop scheduling model, each released job has to be executed on a set of machines in series following the identical route. The criterion of optimality, total k-power completion time (k â¥Â 2) is addressed for this problem. Given its NP-hardness, a branch and bound (B&B) algorithm is designed to obtain the optimal solutions for small-scale problems. On the basis of an initial population generated by the upper bounds of the B&B algorithm, a discrete differential evolution algorithm is introduced to solve medium-scale problems. As the by-product of the B&B algorithm, a sequence-independent lower bound with performance guarantee is presented as a substitute of the optimal solution for large-scale problems. Moreover, the worst-case ratio of the shortest-processing-time-based rule under a consistency condition is provided for the problem. The numerical experiments demonstrate the effectiveness of the proposed algorithms and the new lower bound.
Journal: Computers & Industrial Engineering - Volume 112, October 2017, Pages 336-347