Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates

作者：Bai, Danyu^*

来源：International Journal of Systems Science, 2015, 46(11): 1994-2005.

DOI：10.1080/00207721.2013.843736

• local search
• asymptotic analysis of algorithm
• flow shop
• total quadratic completion time
• scheduling

This paper discusses the flow shop scheduling problem to minimise the total quadratic completion time (TQCT) with release dates in offline and online environments. For this NP-hard problem, the investigation is focused on the performance of two online algorithms based on the Shortest Processing Time among Available jobs rule. Theoretical results indicate the asymptotic optimality of the algorithms as the problem scale is sufficiently large. To further enhance the quality of the original solutions, the improvement scheme is provided for these algorithms. A new lower bound with performance guarantee is provided, and computational experiments show the effectiveness of these heuristics. Moreover, several results of the single-machine TQCT problem with release dates are also obtained for the deduction of the main theorem.

• 出版日期2015-8-18
• 单位沈阳化工大学