论文标题
带有外部资源的单机计划
Single-machine scheduling with an external resource
论文作者
论文摘要
本文研究了单机计划与外部资源的复杂性，该资源是在不间断的时期租用的。需要此外部资源的作业仅在可用的外部资源时才能执行。与工作的安排相关的成本以及与外部资源租赁期间持续时间相关的成本。我们查看具有外部资源的四个类别的问题：一类预算租赁期限的问题，并且需要减少计划成本的时间表，这些问题是预算预算的一类问题，并且需要最小化租赁期限，租赁期和日程安排成本的两类问题都需要最小化，并且要限制了一类租赁费用，以及一部分的成本组合的组合组合。最小化。我们为这四个类别的不同成员提供了彻底的复杂性分析（NP硬度证明和（假）多项式算法）。
This paper studies the complexity of single-machine scheduling with an external resource, which is rented for a non-interrupted period. Jobs that need this external resource are executed only when the external resource is available. There is a cost associated with the scheduling of jobs and a cost associated with the duration of the renting period of the external resource. We look at four classes of problems with an external resource: a class of problems where the renting period is budgeted and the scheduling cost needs to be minimized, a class of problems where the scheduling cost is budgeted and the renting period needs to be minimized, a class of two-objective problems where both, the renting period and the scheduling cost, are to be minimized, and a class of problems where a linear combination of the scheduling cost and the renting period is minimized. We provide a thorough complexity analysis (NP-hardness proofs and (pseudo-)polynomial algorithms) for different members of these four classes.
