스케줄링
-
스케쥴링의 γ(감마)필드스케줄링 2021. 9. 14. 00:40
이번 글은 스케줄링 문제에서의 기본 notation의 마지막 항목인 γ(감마)필드에 대한 글입니다. 그럼 γ(감마)필드에는 어떤 뜻이고 어떤 항목들이 있는지를 살펴보겠습니다. γ(감마)필드의 의미는 schedule문제에서 풀어야 하는 목적함수를 나타냅니다. Schedule 문제에서의 목적은 대부분 목적함수 부분인 γ를 최소화하려 합니다. Schedule 문제에서는 약간씩 컨셉은 다르지만 정해진 job을 최소한의 시간안에 끝내는 것이 목적이기 때문입니다. 문제에서는 보통 단순하게 하나의 목적함수를 최소로 하는 것을 목적으로 하지만, 현실 문제는 여러가지 목적을 동시에 최적화 하려는 경우가 현실입니다. 지금부터 γ(감마)필드에 들어가는 특성과 제약조건들에 대해 알아보겠습니다. γ필드에 들어갈 수 있는 항목 ..
-
스케쥴링의 β(베타)필드스케줄링 2021. 9. 3. 12:28
저번 글에서는 아래 그림에서 α필드가 무슨 뜻이고, 어떤 항목들이 들어가는지에 대해 알아봤습니다. 이번에는 β필드의 뜻과 어떤 항목들이 들어가는지 알아보겠습니다. β필드의 의미는 총 process에서 갖는 특성과 제약조건입니다. 전체 과정에서 제약조건이 없다면 β필드는 비워둘수 있습니다. 반대로 제한사항 및 제약조건은 여러가지가 있을 수 있어 두개 이상이 β필드에 들어갈 수 있습니다. 제한조건으로는 예를 들어서 job의 해결 순서가 꼭 어떤 순서를 지켜야 한다던지, 한던 일을 마무리 하지 않고 다른 작업을 할 수 있다던지 등의 제약조건이 있습니다. 지금부터 β필드에 들어가는 특성과 제약조건들에 대해 알아보겠습니다. β필드에 들어갈 수 있는 항목 (empty) : β필드는 전체공정에서 어떤 특성이나 제약조..
-
스케쥴링의 α(알파)필드스케줄링 2021. 8. 3. 01:37
스케줄링 문제를 접하기 이전에 매우 기본적인 개념과 Notation에 대해 다뤄보겠습니다. 스케줄링 문제에서 나오는 Notation은 매우 많아 대표적인 것들을 우선적으로 다뤄보도록 하겠습니다. 아마 세개의 게시글로 나눠서 순서대로 설명할 예정입니다. 모든 스케줄링 문제에서 job의 개수와 machine의 수가 매우 중요합니다. 그리고 우리가 다루는 스케줄링 문제에서는 job의 개수와 machine의 개수가 유한하다고 가정합니다. 일반적으로 j는 job의 개수를 가리키고, i는 machine의 대수를 나타냅니다. 다음 그림이 schedule problem을 묘사한 표기법입니다. 위의 표기법은 스케줄링 문제를 접하다보면 자주 볼 수 있는 표기법입니다. 위의 표기를 이해하면 문제가 어떤 상황인지, 어떤 조건..
-
NP-Hard / NP-Compelete 의 개념스케줄링 2021. 8. 2. 18:04
P와 NP의 개념을 알면 비교적 NP-Hard와 NP-Compelete를 이해하는 것은 쉬운 편입니다. 우선 NP-Haed의 개념부터 알아보겠습니다. NP-Hard NP-Hard: NP 클래스 안에 있는 모든 문제가 어떤 문제 Q로 Reducible하면, 그 문제 Q는 NP-Hard이다. 위의 정의를 완벽히 이해하기 위해 우선 Redicule의 뜻을 함께 이해해보겠습니다. P와 Q라는 문제가 있다고 해보겠습니다. 그런데 Q를 풀 수있는 알고리즘으로 P를 풀어냈습니다. 그렇다면 문제Q가 P보다 어렵거나 같은 수준의 문제라고 할 수 있습니다. 이런 상황을 Problem P is reducible to Q(to 뒤에 있는게 더 어렵거나 같다)라고 표현합니다!! 여기서 짚고 넘어갈 점은 P를 Q를 풀 수있는 알..
-
P / NP 의 개념스케줄링 2021. 7. 29. 02:00
스케줄링 카테고리의 첫 글이 스케줄링에 관련된 게 아니라서 아이러니하지만, P / NP / NP-Hard / NP-Compelete 개념을 먼저 알고 넘어가는게 좋다고 생각해 첫 게시글을 P / NP / NP-Hard / NP-Compelete를 다루기로 하였습니다. ㅎㅎ 일단 스케줄링 문제들은 보기엔 간단하더라도 대부분 문제를 해결하기가 매우 까다롭습니다. job의 갯수가 세개 라면, 3!으로 총 여섯번의 경우의 수를 탐색해보면 최적의 해를 구할 수가 있겠죠. 그런데 job의 수가 40개이고, job들 마다 ,release time이 다르고, due date와 같은 제약조건이 제각각인 상황에서 최적의 스케줄링을 하라고 하면? 뭐 그냥 간단히 40!의 방법을 다 해보면 될 테지만 40!은 엑셀 함수를 이..