우선순위규칙(Dispatching Rules) (2)

우선순위규칙(Dispatching Rules) (2)


    우선순위규칙의 기초에 대해 간단히 살펴보았습니다. 현장에서 많이 사용되는 우선순위규칙들만을 고려한다 하더라도, 상당히 많은 종류의 우선순위규칙이 있습니다. 우선순위규칙과 관련된 다른 내용을 살펴보기에 앞서, 본 절에서는 우선순위규칙들 중에서 많이 언급되고 있고, 또 사용되고 있는 것을 선별적으로 설명드리도록 하겠습니다. (스케쥴링 문제에 따라 사용되는 dispatching rule도 매우 다양합니다. 본 소개에서는 job-shop 스케쥴링에 사용되는 dispatching rule을 선별적으로 소개드린다는 점을 알려드립니다.)

 이해를 돕기 위한 문제 상황의 예

    다음의 규칙을 쉽게 이해하기 위해 예를 하나 들지요. 지금 기계 MCX 앞에는 3개의 작업이 있습니다. 각 작업의 라우팅을 비롯한 공정진행현황과 관련된 정보는 다음과 같습니다. 

    1. 작업 A : MCA( 10 ) -> MCB( 20 ) -> MCX ( 15 ) 
      작업장 MCX 도착시간 ( 50 ), 납기일 ( 80 )
    2. 작업 B : MCB( 15 ) -> MCX( 10 ) -> MCA ( 30 ) 
      작업장 MCX 도착시간 ( 45 ), 납기일 ( 60 )
    3. 작업 C : MCX( 20 ) -> MCA( 20 ) -> MCB ( 10 ) 
      작업장 MCX 도착시간 ( 40 ), 납기일 ( 70 )

 우선순위규칙의 예

    하단에 언급되는 dispatching rule들은 YIH-LONG CHANG, et al., "Ranking Dispatching Rules by Data Envelopment Analysis in a Job Shop Environment," IIE Transactions Vol. 28, pp. 631-642, 1996. 의 Appendix에서 발췌한 것임을 밝혀둡니다. 

  • SPT(Shortest Processing Time) : 가장 짧은 공정시간을 필요로 하는 작업부터 선택. 작업 A는 15, 작업 B는 10, 작업 C는 20 만큼의 시간을 필요로 함으로, 작업 B 가 선택되겠지요.
  • LTWK(Least Total Work) : 전체 공정시간(공정시간의 합)이 가장 짧은 작업부터 선택. 작업 A는 45(10+20+15), 작업 B는 55(15+10+30), 작업 C는 50(20+20+10) 이므로, 작업 A가 선택되겠지요.
  • LWKR(Least Work Remaining) : 잔여 작업시간이 가장 짧은 작업부터 선택. 작업 A는 15, 작업 B는 40(10+30), 작업 C는 50(20+20+10) 이므로, 작업 A가 선택되겠지요.
  • SRM(Shortest Remaining Time) : 현재 고려중인 공정을 제외한 잔여 작업시간이 가장 짧은 작업부터 선택. 작업 A는 0, 작업 B는 30, 작업 C는 30(20+10) 이므로, 작업 A가 선택되겠지요.
  • SPT/TWK : 고려중인 공정의 소요시간을 전체 공정시간으로 나누어, 그 비율이 가장 작은 작업부터 선택. 작업 A는 15 / 45, 작업 B는 10 / 55, 작업 C는 20 / 50 이니까, 작업 B가 선택되겠지요.
  • SPT/TWKR : 고려중인 공정의 소요시간을 잔여 공정시간으로 나누어, 그 비율이 가장 작은 작업부터 선택. 작업 A는 15 / 15, 작업 B는 15 / 40, 작업 C는 20 / 50 이니까, 작업 B가 선택되겠지요.
  • LPT(Longest Processing Time) : 가장 긴 공정시간을 필요한 하는 작업부터 선택. 작업 A는 15, 작업 B는 10, 작업 C는 20 만큼의 시간을 필요로 함으로, 작업 C가 선택되겠지요.
  • MTWK(Most Total Work) : 전체 공정시간(공정시간의 합)이 가장 큰 작업부터 선택. 작업 A는 45(10+20+15), 작업 B는 55(15+10+30), 작업 C는 50(20+20+10) 이므로, 작업 B가 선택되겠지요.
  • MWKR(Most Work Remaining) : 잔여 작업시간이 가장 긴 작업부터 선택. 작업 A는 15, 작업 B는 40(10+30), 작업 C는 50(20+20+10) 이므로, 작업 C가 선택되겠지요.
  • LRM(Longest Remaining Work) : 현재 고려중인 공정을 제외한 잔여 작업시간이 가장 긴 작업부터 선택. 작업 A는 0, 작업 B는 30, 작업 C는 30(20+10) 이므로, 작업 B 또는 작업 C가 선택되겠지요.
  • LPT/TWK : 고려중인 공정의 소요시간을 전체 공정시간으로 나누어, 그 비율이 가장 큰 작업부터 선택. 작업 A는 15 / 45, 작업 B는 10 / 55, 작업 C는 20 / 50 이니까, 작업 C가 선택되겠지요.
  • LPT/TWKR : 고려중인 공정의 소요시간을 잔여 공정시간으로 나누어, 그 비율이 가장 큰 작업부터 선택. 작업 A는 15 / 15, 작업 B는 15 / 40, 작업 C는 20 / 50 이니까, 작업 A가 선택되겠지요.
  • EDD(Earliest Due Date) : 납기일이 가장 빠른 작업부터 선택. 작업 A는 80, 작업 B는 60, 작업 C는 70 이므로, 작업 B가 선택되겠지요.
  • (MIN)SLACK : 납기일로부터 잔여작업시간을 뺀 여유(SLACK)이 가장 작은 작업을 선택. 작업 A는 65(80 - 15), 작업 B는 20(60-10-30), 작업 C는 20(70-20-20-10)입니다. 따라서, 작업 B 또는 작업 C가 선택됩니다.
  • STS-SLACK : 납기일로부터 전체 공정시간을 뺀 여유(SLACK)이 가장 작은 작업을 선택. 작업 A는 35(80-45), 작업 B는 5(60-55), 작업 C는 20(70-50)이므로, 작업 B가 선택됩니다.
  • SLACK/ROP : SLACK을 잔여공정수로 나누어 가장 작은 작업을 선택. 작업 A는 65/1, 작업 B는 20/2, 작업 C는 20/3 이므로, 작업 C가 선택됩니다.
  • STS-SLACK/ROP : STS-SLACK을 잔여공정수로 나누어 가장 작은 작업을 선택. 작업 A는 35/1, 작업 B는 5/2, 작업 C는 20/3 이므로, 작업 B가 선택됩니다.
  • SLACK/TWK : SLACK을 TWK로 나누어 비율이 가장 작은 작업을 선택. 작업 A는 65/45, 작업 B는 20/55, 작업 C는 20/50 이므로, 작업 B가 선택됩니다.
  • SLACK/TWKR : SLACK을 TWKR로 나누어 비율이 가장 작은 작업부터 선택. 작업 A는 65/15, 작업 B는 20/50, 작업 C는 20/50 이므로, 작업 C가 선택됩니다.
  • FOPR( Fewest Number of Operations Remaining ) : 잔여 공정수가 가장 작은 작업을 선택. 작업 A는 1, 작업 B는 2, 작업 C는 3 이므로, 작업 A가 선택됩니다.
  • MPOR( Most Number Of Operations Remaining ) : 잔여 공정수가 가장 많은 작업부터 선택. 작업 A는 1, 작업 B는 2, 작업 C는 3 이므로, 작업 C가 선택됩니다.
  • FCFS( First Come First Served ) : 가장 먼저 도착한 작업을 먼저 선택합니다. 작업 A는 50, 작업 B는 45, 작업 C는 40 이므로, 작업 C가 선택됩니다.
  • LCFS( Last Come First Served ) : 제일 늦게 도착한 작업을 먼저 선택합니다. 작업 A는 50, 작업 B는 45, 작업 C는 40 이므로, 작업 A가 선택됩니다.
  • RND ( Random ) : 아무 작업이나 선택합니다.
  • WINQ : 다음 공정이 수행될 기계에 부하가 가장 작은 작업을 선택합니다. 예로 보여드리지는 않겠습니다.

 이 외에도 ...
    사실 이 외에도 상당히 많은 우선순위규칙들이 있습니다. 이들 우선순위규칙은 나름대로 합리적인 이유를 가지고 있습니다. 스케쥴링 문제를 잘 이해하고 있다면, 적절한 우선순위규칙을 선택할 수 있을 것입니다. 아울러, 위에서는 소개되지 않았지만, ODD 또는 OPNDD(Operation Due Date)라는 것이 있습니다. 공정별로 due date를 계산한다는 개념인데요, 계산 방법에 따라 많은 variation 이 있답니다. 

    이들 우선순위규칙을 나름대로 분석해보면,
    • 공정 수행 시간
    • 작업 수행 시간 (잔여 작업시간 또는 전체 작업시간)
    • 납기일, 도착시간(생산투입시간)
    • 공정의 수
    • 시스템 congestion level
    에 관한 정보에 기반하고 있으며, 언제나 그 값이 변하지 않는 static한 규칙도 있으며, 시간이 흐름에 따라 그 값이 변하는 dynamic한 규칙도 있습니다.

 다음 시간에는 ...

    다음 시간에는 우선순위규칙과 FCS(Finite Capacity Scheduling)의 관계에 대해 설명을 드리고, 우선순위규칙의 한계를 추가로 설명드리도록 하지요. 그리고, Message Board에 여러분이 남겨주신 질문사항들 중 중요한 것에 대한 답변을 드리도록 하겠습니다. 

    본 페이지는 1998년 4월 14일에 작성되었습니다. 
이 게시물을
Address

39-317, Dept. of Industrial Engineering,

Seoul National University, Shillim-dong, Gwanak-gu,

Seoul, 151-744 Korea

Contacts

+82-2-880-7182

Designed by MAILAB. All Rights Reserved.