Indexed by:Conference Paper

Date of Publication:2018-01-01

Included Journals:CPCI-S、SCIE

Volume:882

Page Number:116-140

Key Words:Flow shop; Bin-packing; Approximation algorithms

Abstract:In this paper, we study a problem of the two-machine flow shop scheduling problem with intermediate transportation. This problem has been studied in [2,4,17]. The best approximation algorithm was presented in [17] with a two approximation ratio to our best knowledge. We propose a (5/3 + epsilon)-approximation algorithm for this problem, where epsilon > 0. Moreover, our algorithm can reach the lower bound 5/3 asymptotically given by [2] when epsilon is close to 0.