이동 작업

Question

가 매우 어려운 동적 프로그래밍 질문, 내가 당신과 함께 공유하고 싶은 우리의 솔루션으로 조금 논의 할 준비 때 가장 낮은 비용을 얻는 방법 : 당신은 당신의 새로운 응용 프로그램을 넣어 것입니다

을 클라우드 서버; 최저 비용을 얻으려면 직업을 예약해야합니다. 동일한 서버에서 동시에 실행중인 작업 수에 대해 신경 쓸 필요가 없습니다. 모든 작업 k는 릴리스 시간 sk, 마감 시간 fk 및 dk ≤ fk-sk 인 지속 시간 dk에 의해 주어집니다. 이 작업은 시간 sk와 fk 사이에 dk 연속 분 간격으로 예약해야합니다. 서버 회사는 서버 당 분당 요금을 부과합니다. 하나의 가상 서버 만 있으면되므로 작업을 실행하지 않고 시간을 최대화하기 위해 sk에서 fk로 작업 이동 작업을 절약 할 수 있습니다. 즉, 하나 이상의 작업을 실행하는 시간을 최소화 할 수 있습니다. 동적 프로그래밍을 사용하여 문제를 해결합니다. 귀하의 알고리즘은 작업 수 인 n에서 다항식이어야합니다.

Answer 1

이것은 바쁜 시간을 최소화하는 문제입니다.

참조 정리 17 this paper의 :

Rohit Khandekar, 바룩 쉬버,하다 스 Shachnai, 그리고 태미 타 미르. 여러 컴퓨터 실시간에서 바쁜 시간 최소화. 일정. 다항식 시간 알고리즘에 대한 설명은 180, 2010

- 소프트웨어 기술의 기초와 이론 컴퓨터 과학 (FSTTCS)에 30 연례 학술 대회, 페이지 169합니다.

의 핵심은 다음과 같습니다

1. 당신이 일정이 경우 작업 중 하나에 대한 기한을 칠 때까지, 각 바쁜 간격을 지연 고려 (고려 될 필요가 특정 흥미로운 시간이있다 실현하기 위해 처리 중)

2. 가장 긴 지속 작업이 수행 된 시점을 고려해야합니다. 이것은 문제를 두 조각으로 나눕니다. 이전과 이후, 이것은 보통 동적 프로그래밍 방식으로 독립적으로 해결 될 수 있습니다.