As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in cloud computing and introduced by Chen et al. [3] recently. A set of two-stage jobs are selected and scheduled on parallel two-stage flowshops to achieve the maximum total profit while maintaining the given makespan constraint. We give a positive answer to an open question about its approximability proposed by Chen et al. [3]. More specifically, based on guessing strategies and rounding techniques for linear programs, we present a polynomial-time approximation scheme (PTAS) for the case when the number of flowshops is a fixed constant.

翻译：作为平行两阶段流动商店问题和多环形问题的一个混合体,我们调查了平行两阶段流动商店的时间安排,这是由云计算应用和陈等人最近提出的[3] 驱动的,在平行两阶段流动商店中挑选和安排了一系列两阶段工作,以实现最大总利润,同时保持给定的平衡限制。我们积极回答陈等人提出的有关其近似性的未决问题[3]。更具体地说,根据对线性程序的战略和圆形技术的猜测,我们为流动商店数目固定不变的情况,我们提出了一个双阶段近似计划(PTAS)。