단일 기계의 전체 지각을 최소화하는 정확한 알고리즘을 구현하려고합니다. 웹에서 동적 프로그래밍을 사용하여 구현할 수있는 아이디어를 찾고있었습니다. 나는 77 년에 PSEUDOPOLYNOMIAL 알고리즘을 제안한 Lawler의 논문을 읽었다. 그러나 여전히 자바 또는 C# 코드로 매핑 할 수 없었다.알고리즘 - 전체 지각 최소화
이 정확한 알고리즘을 효과적으로 구현하는 방법에 대한 참조를 제공해 주시겠습니까?
편집 1 : @bcat : 실제로는 아닙니다. 소프트웨어 용으로 구현해야합니다. :(여전히 나는 욕심 하나를 쉽게 구현할 수있다. 그것을 구현하는 방법에 어떤 지침을 찾을 수 없습니다,하지만 일정의 결과는 인상적이 아니다.
친절 감사,
Xiaon
아마를 스토니 브룩 알고리즘 저장소의 Job Scheduling Section는 당신을 도울 수 있습니다.
당신은 다른 변수에 대한 한계와 입력의 전반적인 특성과 함께 특정 문제의 정확한 특성을 지정한 수.
이 정의를 사용하지 않는다면 다음 정의를 사용한다고 가정합니다.
n 개의 독립적 인 작업 (각각은 처리 시간과 만기 날짜가 있음)으로 단일 기계 스케줄링 문제에서 전체 지각을 최소화하고자합니다.
겹쳐 쓰지 않도록 작업의 하위 집합을 선택하고 (수행 할 수있는 단일 시스템) 작업 일정을 선택하고 마감일을 지켜야합니다.
내가해야할 첫 번째 단계는 기한을 기준으로 정렬하는 것인데, 다른 방법으로 정렬하는 것의 이점이없는 것 같습니다.
다음으로 남은 것은 부분 집합을 선택하는 것입니다. 다음은 동적 프로그래밍이 도움이되는 곳입니다. 나는 상태와 재귀 관계를 설명하려고 노력할 것이다.
주 :
[current time][current job] = maximum number of jobs done
관계 :
당신은 현재 작업을 처리하고
f(current time + processing_time_of[current job],current job +1)
전화를 걸거나이 과정을 생략하고 전화 중
f(current time,current job +1)
마침내 당신은 그 호출에 의해 반환 된 두 값의 최소값을 가지고 상태
[current time][current job]
에 저장 그리고 당신은 시간 0 일 0에서 재귀를 시작합니다.그런데
, 욕심이 꽤 잘하고있는 것 같다,이 체크 아웃 :
하나의 기계에 대한 http://www.springerlink.com/content/f780526553631475/
당신이 경우, (또한 감소 타임 알고리즘이라고도 함) 가장 긴 처리 시간 일정이 최적 사전에 모든 작업을 알고 가장 길게부터 가장 짧은 것으로 정렬 할 수 있습니다 (따라서 정렬 만하면됩니다).
이미 언급했듯이 스케줄링 문제에 대한 정보는 지정하지 않았으므로이 문제를 해결하는 데는 어려움이 있습니다 (보편적으로 최적 인 및 효율적인 스케줄러가 없기 때문입니다).
이 숙제가 있습니까? – bcat