종속성을 사용하여 단위 작업 스케줄링에서 이익 극대화

Question

문제 작업 간 종속성이있는 머신을 무제한으로 P 개의 시간에 예약 할 n 개의 작업이 있습니다. 모든 직업에는이 일이 끝난 후에 만 ​​예정된 일자리가 있습니다. 어떤 기계에서든지 ^번 작업을 ^번 초로 예약하는 이익은 f (i, j)이며, 이는 양수입니다.
목표는 각 작업을 최대 P 초에 한 번 정확하게 예약하여 총 이익을 극대화하는 것입니다.

모든 작업을 항상 P 초로 예약 할 수 있다고 가정 할 수 있습니다.

모든 것이 미리 알려 지므로 오프라인 문제입니다.

또한 0 < = f (i, j) < = B. 모든 i, j에 대해.

이고 종속성 개수는 O (n)입니다.

이 문제는 간단합니까? 수익은 시간이 독립적 인 첫 일자리를 그 가정,

내 접근 편의상
[유한 제약 때문일 수 있습니다].
f (i, j)는 모든 i에 대해 j와 독립적이며 i에만 종속됩니다.
그러면 P 초 안에 맞는 모든 토폴로지 순서가 작동합니다.
의존성이 없다면, 우리는 또한 각 직업에 대한 시간을주는 최고의 이익을 선택합니다. 이것은 또한 쉽습니다.

그러나 문제는 작업에 대한 이익이 종속성으로 인해 시간에 따라 달라지는 경우입니다.이 경우 모든 일반 알고리즘을 생각할 수 없습니다.

작업 간의 종속성을 처리하는 데 문제가 있습니다. 온라인으로 알고리즘을 예약하는 종속 장치 작업을위한 리소스가 있습니까?

도움이 될 수있는 아이디어를 공유하시기 바랍니다 ...

업데이트 : 그들은이 문제의 분석을 위해 요구 될 수있는 I는 다양한 매개 변수에 대한 경계를 추가했습니다.

Answer 1

이것은 동적 프로그래밍 문제입니다. 단순함을 위해 모든 이익이 음수가 아니라고 가정합시다.

'또는 나중에 j보다 작업 일 및 (아래로 재귀 적으로)에 의존 모든 것들을'초 일, 또는 -1 그건 불가능 인 경우 i 일정에서 만들 수있는 최대 이익으로 F(i, j) 정의 . 종속성 i의 i_1위한 -1이다 -1F(i_1, j+1) 경우

그럼 F(i, j)이다. 그렇지 않은 경우 (f(i, j) + F(i_1, j+1)) 또는 F(i, j+1) 중 큰 값입니다.

그리고 대답은 모든 작업 i에 대해 F(i, 0)의 합계입니다.

(이 문제가 NP-하드 될 것 무제한 기계없이 ...) 여기

---

각 절은 부정 모든 조건이 곳 MAX-SAT 방정식을 모델링 문제를 사용하는 방법의 예입니다 또는 모든 조건이 무효화됩니다.

우리는 4 개의 부울 변수 A, B, C 및 D이 있다고 가정합니다. 예를 들어 방정식 (A && B) || (!A && !C) || (!B && !C && !D) || (C && D)에 대한 최대 만족 가능성을 가정한다고 가정합니다. (!이 아닌, && 수단, 및 || 수단 또는를 의미 곳.)

는 이제 J1이 J2 전에 실행하는 작업에 대한 표기 J1 > J2을 사용하자. J1 > (J2, J3)은 J1) is a dependency for both J2 and J3`을 의미하도록 괄호로 묶어서 배포하십시오.

이제 불리언 모델을 작성하여 12 가지 작업을 설정해 보겠습니다. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3 및 D1 > D2 > D3. 그런 다음 작업 A2, B2, C2, D2은 시간 2 또는 3에서 발생해야하며 부울 A은 "A2 시간 2에 발생합니다."진술입니다. 그리고 다른 불리언들도 마찬가지입니다.

이들 작업은 모두 그들이 실행 시간에 관계없이 1의 이익을 얻습니다. 우리는 불린만큼 많은 일자리를 3 배로 도입했지만, 지금까지 이것은 간단합니다.

이제 절에 대한 작업을 추가해 보겠습니다. 이들 각각의 작업은 2 또는 3 초 단위로 실행되는 경우 11의 이익을 가지며 그렇지 않은 경우 1입니다. 그러므로 최대 절 이익을 얻을 수있는 부울에 대한 설정을 찾으면 최대 이익에 도달하게됩니다.

(A2, B2) > J1(A && B)의 진상을 모델링하십시오.

J2 > (A2, C2))(!A && !C)의 진실을 모델링합니다.

J3 > (B2, C2, D2)(!B && !C && !D)의 진실을 모델링합니다.

(C2, D2) > J4(C && D)의 진실을 모델링합니다.

이 작업은 추가 된 작업 수가 절의 수와 같은 간단한 직선 변환입니다.

그래서 우리는 스케줄링을 통해 MAX-SAT 문제를 모델링합니다. 그러나 우리는 그것들 모두를 모델링 할 수 없습니다. 특히 우리는 (A && !B)과 같은 부정적인 부정을 가진 절을 모델링 할 방법이 없습니다. 따라서 MAX-SAT가 NP 하드 일지라도이 제한된 버전은 가능하지 않을 수 있습니다. 그러나 MAX-SAT의 다른 제한된 버전들, 예를 들어 MAX-2SAT는 NP 하드 인 경향이 있으며, 이것이 또한 내 직감입니다.

그러나 직감을 증명하거나 반증하기 위해서는보다 적절한 포럼에서 질문해야합니다. https://cs.stackexchange.com/처럼.