An FPTAS for scheduling with piecewise linear decreasing processing times to minimize makespan
An FPTAS for scheduling with piecewise linear decreasing processing times to minimize makespan
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Min Ji;C. E. Cheng
中科院分区：
文献类型：
--
作者：
Min Ji;C. E. Cheng
研究了单机和多台平行机上的非抢占式工件排序问题，其中工件的加工时间是工件开始时间的分段线性非增函数。目标是最小化makespan。我们首先给出了一个完全多项式时间近似方案（FPTAS）的情况下，一台机器。然后，我们推广的结果的情况下，有m个相同的机器。
We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomialtime approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.