并行作业调度恶化的工作并可能破坏机器

我们考虑在具有破坏性的环境中对恶化的作业进行并行计算机调度，在该环境中，某些计算机由于潜在的干扰而变得不可用。 这意味着某些机器的中断可能会在特定时间发生，该中断将以一定概率持续一段时间。 如果作业在处理期间被中断的机器中断，并且不需要（需要）在机器再次可用后重新启动，则称为可恢复（不可恢复）情况。 所谓作业恶化，是指作业的实际处理时间在计划以后进行处理时会增加，因为由于机器的使用和老化，机器效率会随着时间而下降。 但是，维修过的机器将恢复其原始效率状态。 我们考虑两种情况，即发生故障时立即对发生故障的机器执行维护，而不进行机器维护。 在每种情况下，目标都是确定最佳计划，以在不可恢复和可恢复的情况下最大程度地减少作业的预期总完成时间。 我们确定问题各种情况的计算复杂度状态，并在可行的情况下为它们提供伪多项式时间求解算法和完全多项式时间逼近方案。