스케쥴링 문제에 대한 해법
스케쥴링 문제에 대한 해법
- 발견적 기법 :
고전적인 문제에서 좋은 해를 빨리 찾는 발견적 기법은 학계의 꾸준한 관심사이고, 많은 연구들이 보고되고 있지만 몇 가지를 제외하고는 널리 인정받지 못하는 것 같습니다. 그러나, 많은 발견적 기법들은 일반적인 상황에서 항상 좋은 해를 생성하는 것을 목적으로 하는 것이 아니라, 특정 상황에 적합한 방법으로 개발된 것임도 항상 염두에 두어야 합니다. - 우선순위규칙 :
실제 현장에서 가장 널리 사용되는 방법의 하나가 아마 우선순위규칙일 것입니다. 우선순위규칙은 나름대로의 합리적인 이유를 바탕으로 설계되었다고 할 수 있지만, 문제의 상황에 따라 늘 좋은 결과를 보여주는 것도 아니며, 항상 좋은 성능을 일관되게 보장하는 우선순위규칙은 존재하지 않는 한계를 가지고 있습니다. 우선순위규칙은 이해하기도 쉽고, 스케쥴링의 기초이기 때문에 조만간에 추가 설명을 드리도록 하겠습니다. - 추계적 최적화 :
컴퓨터 기술(H/W 기술)의 발전과 더불어 몇 년전부터 각광을 받은 분야가 추계적 최적화 분야라고 할 수 있습니다. 이 분야의 연구들은 잘 정형화된 문제에서 좋은 성능을 보이고 있지만, 조금만 더 복잡한 문제(현실성 있는 문제)에 적용하기 위해서는 많은 노력을 필요로 합니다. 문제 자체를 표현하기가 어렵기 때문이지요. 대표적인 방법들로는 Genetic Algorithm, Tabu Search, Simulated Annealing 등이 있습니다. - 전문가 시스템, 인공 지능의 활용 :
그리고, 전문가 시스템(Expert System)이나 인공지능(Artificial Intelligence)을 이용한 스케쥴링 방법이 있습니다. 이 분야는 상당한 잠재력을 가지고 있음에도 불구하고, 시스템 개발에 드는 노력이 매우 크기 때문에 제한적으로 활용되고 있습니다. 대개 정형화된 문제에 적용하기 보다는 매우 복잡한 제약조건을 가지고 있는 문제에 적용되고 있습니다. 이전에는 production rule에 기반한 rule-based system이 주를 이루었지만, 최근에는 CSP(Constraint Satisfaction Problem) 접근 방법이 많은 각광을 받고 있습니다. CSP는 전산학에서 태동되어, temporal reasoning을 비롯하여 vision, robot planning, knowledge representation 등에 활용되어 왔으며, OR(Operations Research) 분야의 이론과 접목을 통해 빠른 성장을 하고 있습니다. - 기타 :
이 외에도 사실 많은 방법들이 있답니다. 이 후 스케쥴링을 이야기할 때에 빼놓을 수 없는 병목(bottleneck)이나 분해(decomposition) 등을 이야기하면서 앞서 설명드린 방법들이나 기타 방법들을 간간이 소개드리도록 하지요.
우리가 현실에서 접하게 되는 대부분의 스케쥴링 문제는 매우 복잡하며, 난이도가 높습니다. 따라서, 대개 스케쥴링 시스템을 설계할 때에는 무엇보다도 '소요 시간'과 '해의 질(quality)'를 반드시 고려해야 합니다. 어떤 상황에서는 스케쥴을 몇 초 이내에 구해야 하는 경우도 있지만, 어떤 상황에서는 몇 일에서 몇 주일이 걸려도 상관없는 경우도 있습니다. 이렇게 사용자가 원하는 시간내에 해를 생성해야 한다는 조건이 실시간 스케쥴링('real-time scheduling')입니다. 여러분이 키보드를 눌러 명령을 실행시키자마자, 답이 나오는 것이 반드시 실시간('real-time') 처리는 아니라는 것이지요. 그리고, 또 중요한 것이 '해의 품질'입니다. 물론, 최적해를 찾고 싶지만, 계산능력의 한계로 최적해를 구하기 힘든 경우에는 가능한 좋은 해를 얻고 싶어할 것입니다. '계산 소요 시간'과 '해의 질'간에는 trade-off 관계가 있기 때문에, 적절한 타협안을 만들어야 겠지요. 그리고, 스케쥴링 시스템들이 왜 실패해 왔는가? 를 설명드리면서, 언급되겠지만 상황에 따라서는 최적해를 반드시 구해야 하거나 최적해만이 능사는 아니라는 사실도 염두에 두어야 합니다.
앞서, 스케쥴링 문제를 분류한 바 있습니다. 여러분이 접한 스케쥴링 문제를 분류할 수 있다면 해당 분야의 기존 연구들을 이용하여 스케쥴링 시스템을 만드는 데 이용할 수 있습니다. 스케쥴링 방법으로는 어떤 것들이 있을 수 있을까요? 제조 시스템의 특성에 따라 매우 큰 차이가 있기 때문에, 획일적으로 나눈다는 것은 불가능하지만 잡샵(job shop)의 경우를 예로 들어 설명드리도록 하지요. (생산관리를 전공하셨거나, 생산관리를 전공중인 분들은 매우 잘 아시리라 생각됩니다.)
가장 널리 사용되는 방법은 아마도 발견적기법(heuristic methods)이 아닌가 싶습니다. 작업이나 공정의 특성, 자원의 배치나 가용도 등을 나름대로 잘 파악하여, 상황에 맞는 방법을 사용하고 있지 않나 싶습니다. 물론, 이러한 방법도 적용 과정 뿐만 아니라 구현이 끝난 후에도 끊임없는 검토작업을 통해 개선을 해나거나 수정해 나가야 할 필요가 있습니다. (기회가 닿으면, Goldratt 교수의 TOC(Theory of Constraint)를 소개드리도록 하지요. TOC는 여러 방면에 활용될 수 있지만, 스케쥴링 시스템을 비롯한 생산관리 시스템의 설계 및 구현에 활용될 수 있습니다. '병목도 뒤집으면 병목이 아니다' (엘리 골드렛, 새길출판사, 1992)이라는 유명한 책은 Goldratt 교수의 TOC 이론이 거의 정립되어갈 시점에 나온 것이라고 합니다. 스케쥴링을 떠나 MRP/ERP에 관심이 있으신 분들은 꼭 읽어보시기를 권합니다. 소설처럼 쓰여졌음에도 불구하고, 많은 내용이 담겨져있고, 이해하기 쉽도록 설명되고 있습니다. 가격은 7,000원이고요, 인터넷 서점을 통해서도 구입하실 수 있습니다. 광고 끝! ^_^ )
시스템마다 다른 발견적 기법이 사용된다 하더라도, 그 근간을 이루는 방법들이 있습니다. 그 근간을 이루는 방법들을 한 번 정리해보도록 하지요. 최적해를 구하는 방법으로는 (1) 혼합정수계획법(MIP, Mixed Integer Programming), (2) Branch & Bound, (3) 동적계획법(Dynamic Programming) 등이 이용됩니다. 스케쥴링 문제의 일부분에 대한 최적화를 한다거나, 문제가 크지 않다면 이런 방법이 이용될 수 있겠지만, 대부분의 경우 실제 문제에 적용하기에는 방대한 계산량(계산소요시간)때문에 곤란합니다. 해보지도 않고, 어렵다고 포기하는 것은 어리석은 행동이겠지요? 앞서 말씀드린 바와 같이 '소요 시간(반응 시간)'과 '해의 품질'간에는 trade-off가 존재하며, 좋은 해를 반드시 필요한 상황도 있습니다. 이런 상황에서 최적화 방법은 선택이 아니라 필수이겠지요. 실제로 많은 APS(Advanced Planning & Scheduling) 팩키지나 SCM(Supply Chain Management) 팩키지 들에서는 Branch & Bound 와 같은 최적화 방법들이 많이 이용되고 있다고 합니다.
그 외의 방법들은 근사최적해 또는 좋은 해를 구하는 방법이라고 나누어볼 수 있겠는데요, (1) 발견적 기법(Heuristics), (2) 우선순위규칙(Dispatching Rule), (3) 추계적 최적화(Stochastic Optimization) 방법들, (4) 전문가 시스템이나 인공지능을 활용한 방법들 등이 있습니다.
스케쥴링에 관심을 가지고 계셨거나, 생산관리를 전공하신 또는 전공하시고 계시는 분들에게는 진부한 이야기였으리라 생각됩니다. 실제 현장에서 다반사로 이루어지는 '관행'이라는 것을 어떻게 해석해야 할까요? 잘 분석해보면, '관행'도 합리적인 사고나 나름대로의 이유를 바탕으로 하고 있습니다. 관행을 잘 분석하면, '목적'이나 가장 중요하게 여겨지는 제약조건과 같은 정보를 얻을 수 있지요. 합리적인 부분은 받아들이고, 비합리적인 부분은 설득과 노력을 통해서 개선해 나가야 겠지요. 그리고, 개선을 위해서는 대안이 있어야 겠지요. 이런 대안은 해당 분야에 대한 지식을 바탕으로 하고요. 합리적인 사고와 지식을 넓힐 수 있는 좋은 연구 분야가 '스케쥴링'이 아닌가 싶습니다.
본 페이지는 1998년 4월 7일에 작성되었습니다.