A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs
A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs
复制标题
DOI：
10.1007/3-540-44676-1_16
复制
发表时间：
2001-08
期刊：
影响因子：
--
通讯作者：
Eric Angel;E. Bampis;A. Kononov
中科院分区：
文献类型：
--
作者：
Eric Angel;E. Bampis;A. Kononov
考虑一类经典的排序问题，即在一组不相关的机器上排序一组独立的工件。我们有一组n个单处理器作业和m台机器，其中每个作业都要在没有抢占的情况下处理。在机器i上执行作业需要时间pij ≥ 0，并产生成本costcij。我们的目标是找到一个时间表之间取得折衷的最大完工时间和总成本。我们关注的情况下，机器的数量是一个固定的常数，我们提出了一个简单的FPTAS计算任何ε > 0的时间表，最大完工时间为（1 + ε）T和成本最多Copt（T），给定存在一个时间表的最大完工时间T，其中Copt（T）是最小成本时间表的成本，实现了最大完工时间T。我们表明，最佳的完工成本权衡（帕累托）曲线可以近似由一个有效的多项式时间算法在任何所需的精度。我们的结果也可以应用到调度问题中的工件被拒绝是允许的。每个作业都有一个与之相关的惩罚，并且允许调度作业的任何子集。在这种情况下，目标是最小化已调度工件的完工时间和被拒绝工件的总惩罚。
We consider the classical problem of scheduling a set of independent jobs on a set of unrelated machines with costs. We are given a set ofnmonoprocessor jobs andmmachines where each job is to be processed without preemptions. Executing jobjon machineirequires timepij≥ 0 and incurs costcij. Our objective is to find a schedule obtaining a tradeoff between the makespan and the total cost. We focus on the case where the number of machines is a fixed constant, and we propose a simple FPTAS that computes for any ε > 0 a schedule with makespan at most (1 + ε)Tand cost at mostCopt(T), in time, given that there exists a schedule of makespanT, whereCopt(T) is the cost of the minimum cost schedule which achieves a makespan ofT. We show that the optimal makespan-cost trade-off (Pareto) curve can be approximated by an efficient polynomial time algorithm within any desired accuracy. Our results can also be applied to the scheduling problem where the rejection of jobs is allowed. Each job has a penalty associated to it, and one is allowed to schedule any subset of jobs. In this case the goal is the minimization of the makespan of the scheduled jobs and the total penalty of the rejected jobs.