论文标题
在makepan约束下的平行两阶段流程商馆的多项式时间近似方案
A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint
论文作者
论文摘要
作为平行的两阶段流量工厂问题和多背问题问题的混合体，我们研究了MakePAN约束下平行的两阶段流程商店的调度，这是由Cloud Computing中的应用和Chen等人引入的。 [3]最近。选择一组两阶段的作业，并安排在平行的两阶段流交商店上，以达到最大的总利润，同时保持给定的Makepan约束。我们对Chen等人提出的有关其近似性的开放问题给出了积极的答案。 [3]。更具体地说，基于线性程序的猜测策略和四舍五入技术，我们为流程数为固定常数的情况提供了多项式时间近似方案（PTA）。
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.
