论文标题
平行多阶段开放式商店的有效多项式时间近似方案
An efficient polynomial-time approximation scheme for parallel multi-stage open shops
论文作者
论文摘要
实际生产过程和计划领域的新研究领域产生了各种新的调度问题。我们研究了平行的多阶段开放式商店问题，该问题概括了经典的开放式商店调度和并行机器调度问题。鉴于相同的K型开放式商店和一组N工作，我们的目标是在不允许工作的限制下，以最低的Makepan（即最后一份工作的完成时间）处理这些开放式商店的所有工作。对于M和K恒定的情况，我们提出了有效的多项式近似方案（EPTA）。我们EPTA的主要思想是几种分类，缩放和线性编程四舍五入技术的组合。首先对工作和/或操作进行缩放，然后仔细分类为多种类型，以便适当地安排不同类型的作业和/或操作，而不会过多增加MakePan。
Various new scheduling problems have been arising from practical production processes and spawning new research areas in the scheduling field. We study the parallel multi-stage open shops problem, which generalizes the classic open shop scheduling and parallel machine scheduling problems. Given m identical k-stage open shops and a set of n jobs, we aim to process all jobs on these open shops with the minimum makespan, i.e., the completion time of the last job, under the constraint that job preemption is not allowed. We present an efficient polynomial-time approximation scheme (EPTAS) for the case when both m and k are constant. The main idea for our EPTAS is the combination of several categorization, scaling, and linear programming rounding techniques. Jobs and/or operations are first scaled and then categorized carefully into multiple types so that different types of jobs and/or operations are scheduled appropriately without increasing the makespan too much.
