작업 시퀀싱 문제의 목적은 자신의 기한 내에 완료 작업의 순서를 찾아 최대의 이익을 제공하는 것입니다.
마감일과 관련된 일련의 작업이 주어지고 이익이 적립되고 마감일까지 작업이 완료된 경우. 이러한 작업은 최대 이익이되는 방식으로 주문해야합니다.
한 가지 예를 들어 보겠습니다. 그림 1.1 과 같이 모든 작업에 마감일이 있고 마감일 이전에 작업이 완료된 경우 관련 이익이 있는 작업 배열이 제공됩니다. 또한 모든 작업에는 단일 시간 단위가 소요되므로 모든 작업에 대한 가능한 최소 마감일은 1 입니다. 한 번에 하나의 작업 만 예약 할 수있는 경우 총 이익을 극대화하는 방법.
간단한 해결책은 주어진 작업 집합의 모든 하위 집합을 생성하고 해당 하위 집합에서 작업의 타당성을 위해 개별 하위 집합을 확인하는 것입니다. 가능한 모든 하위 집합 중에서 최대 이익을 추적하십시오. 이 솔루션의 시간 복잡성은 기하 급수적입니다.우리는 또한 간단한 해결책보다 더 최적의 욕심 많은 방법을 사용하여이 문제를 해결할 수 있습니다.따라서 욕심 많은 방법을 통해이 문제를 해결할 수 있습니다.
욕심 많은 방법을 통해 작업 시퀀싱 문제를 해결하려면 다음 단계를 수행하십시오:
- 정렬 이익의 순서를 감소하는 모든 작업.
- 결과 시퀀스를 정렬된 작업의 첫 번째 작업으로 초기화합니다.
- 나머지 엔-1 작업에 대해 다음을 수행하십시오.
- 현재 작업이 마감일을 놓치지 않고 현재 결과 시퀀스에 맞출 수 있는 경우 결과에 현재 작업을 추가합니다. 그렇지 않으면 현재 작업을 무시하십시오.
당신이 그림에서 볼 수 있듯이 1.1 작업은 이익의 감소 순서에 이미.여기서 작업 1 은 가장 높은 수익을 가지며 마감일은 3 이므로 그림 1.2 와 같이 2-3 사이에 작업을 설정하십시오.작업 2 는 두 번째로 높은 이익을 가지고 있으며 마감일은 4 이므로 3-4 사이에 해당 작업을 설정하고 모든 사람에게 동일한 작업을 수행합니다 jobs.So 이 경우 총 수익은 110 입니다.
이 알고리즘의 코드는https://www.geeksforgeeks.org/job-sequencing-problem에서 선호할 수 있습니다.그것은 분리 된 데이터 구조에 의해 최적화 할 수 있습니다.
당신이 기사를 좋아 바랍니다.감사합니다:)
