스케쥴링의 α(알파)필드

스케줄링 문제를 접하기 이전에 매우 기본적인 개념과 Notation에 대해 다뤄보겠습니다. 스케줄링 문제에서 나오는 Notation은 매우 많아 대표적인 것들을 우선적으로 다뤄보도록 하겠습니다. 아마 세개의 게시글로 나눠서 순서대로 설명할 예정입니다. 

 

모든 스케줄링 문제에서 job의 개수와 machine의 수가 매우 중요합니다. 그리고 우리가 다루는 스케줄링 문제에서는 job의 개수와 machine의 개수가 유한하다고 가정합니다. 일반적으로 j는 job의 개수를 가리키고, i는 machine의 대수를 나타냅니다.  

 

다음 그림이 schedule problem을 묘사한 표기법입니다. 

위의 표기법은 스케줄링 문제를 접하다보면 자주 볼 수 있는 표기법입니다. 위의 표기를 이해하면 문제가 어떤 상황인지, 어떤 조건이 있는지 없는지, 무엇을 구하는 문제인지를 한번에 알 수 있는 간단하면서도 기본적이게 문제의 설명을 축약한 표기입니다.

 

α필드 부터 무슨 의미인지 살펴보겠습니다. 그리고 이번 (1)게시글에서는 α에 대해서 집중적으로 다룰 것입니다. α필드에는 하나의 항목만이 들어갈 수 있고 machine의 환경을 의미합니다. 그럼 지금부터 α필드에 들어가는 항목을 살펴보겠습니다. 

 

 

α필드에 들어갈 수 있는 항목

---

◈ Single machine and machines in parallel

1: Single machine의 경우입니다. 말 그대로 machine이 한대만 있는 경우 입니다.

 

Pm: m개의 동일한 기계가 parallel로 있는 경우입니다. 동일한 기계이므로 기계의 성능은 같습니다. 

 

Qm: m개의 기계가 parallel로 있는 경우입니다. 이 경우에 기계의 성능은 다릅니다. 성능이 다르다는 것은 같은 job을 해결하는 속도가 다르다고 이해하면 쉽습니다. pij는 job j가 machine i에서 머무르는 시간을 가르키고 pj/vi로도 나타낼 수 있습니다. 

 

Rm: Qm의 보다 일반화한 경우입니다. m개의 전혀 다른 기계가 parallel로 존재합니다. machine i는 job j를 vij 속도로 처리할 수 있습니다. 

 

◈ Machines in series 

Fm: Flow shop을 나타냅니다. 밑의 그림은 m이 4인 경우로 4개의 machine이 일렬로 있고, 모든 작업이 나열된 machine에서 차례대로 처리됩니다. 

FFc: Flexible Flow shop을 나타냅니다. 아래의 그림은 Flexible Flow shop을 나타낸 그림입니다. flow shop의 경우 stage마다 한대의 기계가 있지만 여기서는 동일한 기계 여러대가 stage를 이루고 있습니다. c는 stage의 개수입니다. 마찬가지로 모든 작업이 순서대로 모든 stage를 거쳐가며 차례대로 처리됩니다. 

Jm: Job shop을 나타냅니다. m개의 machine이 일렬로 있지만 job들이 순서대로 machine을 거치며 처리되는 것이 아니라 자체 라우팅을 가지고 있습니다. (모든 machine에서 처리될 필요가 없습니다.)

 

FJc: Flexible Job shop입니다. Flexible Flow shop과 동일한 기계환경이 있지만 Job shop의 성격대로 job들이 각자의 라우팅을 가지고 있습니다. 마찬가지로 c는 stage의 개수를 나타냅니다. (모든 machine에서 처리될 필요가 없습니다.)

 

Om: Open shop입니다. 각 job들이 모든 machine에서 처리되어야 하지만, 각자의 라우팅을 가지고 있는 경우입니다. 

 

 

여기까지 α필드에 들어가는 항목들을 살펴보았습니다. 기본적인 Notation을 이해해야 문제로 들어갈 수 있기 때문에 조금 길더라도 나눠서 다음 글에서는 β, γ순으로 무엇을 뜻하고, 어떤 항목들이 들어가는지 알아보겠습니다.