교대 할당을위한 알고리즘 (이산 최적화 문제)

StackOverflow https://stackoverflow.com/questions/573670

문제

병원의 간호사에게 변화를 최적으로 할당하는 응용 프로그램을 개발하고 있습니다. 나는 이것이 A라고 믿는다 선형 프로그래밍 불연속 변수의 문제이므로 아마도 NP-HARD :

  • 매일 각 간호사 (약 15-20)가 교대로 할당됩니다.
  • 다른 교대의 적은 수 (약 6 장)가 있습니다.
  • 하루 또는 emplyoee와 관련하여 상당한 수의 제약 및 최적화 기준이 있습니다.
    • 매일 교대마다 할당 된 최소 수의 사람들이 있어야합니다.
    • 중간 시프트를하는 사람이 있으면 조기 교대에 한 사람이 적을 수 있도록 일부 이동이 중복됩니다.
    • 어떤 사람들은 조기 교대를 선호하고 일부는 늦은 교대를 선호하지만 여전히 더 높은 시프트 업무 급여를 얻으려면 최소한의 교대 변화가 필요합니다.
    • 한 사람이 하루 늦게 근무하고 다음 날 조기 교대 근무를 할 수 없습니다 (최소 휴식 시간 규정으로 인해)
    • 할당 된 근무 주 길이 회의 (사람들의 경우 다른)
    • ...

따라서 기본적으로 많은 숫자 (AOUT 20*30 = 600) 변수가 있으며 각각은 적은 수의 이산 값을 취할 수 있습니다.

현재 내 계획은 수정 된 것을 사용하는 것입니다 Min-Conflicts 알고리즘

  • 임의의 과제로 시작하십시오
  • 각 사람과 매일 피트니스 기능이 있습니다.
  • 최악의 피트니스 가치로 사람 또는 하루를 선택하십시오.
  • 그 날/사람의 과제 중 하나를 무작위로 선택하고 최적의 체력 값을 초래하는 값으로 설정하십시오.
  • 최대 반복 수에 도달하거나 선택한 날/사람의 개선이 찾을 수 없을 때까지 반복하십시오.

더 나은 아이디어가 있습니까? 나는 그것이 현지 최적에 갇히게 될까 걱정하고있다. 어떤 형태의 형태를 사용해야합니까? 시뮬레이션 어닐링? 또는 한 번에 하나의 변수의 변화뿐만 아니라 특히 두 사람 사이의 변화 전환 (현재 매뉴얼 알고리즘의 주요 구성 요소)을 고려합니까? 알고리즘을 현재 제약 조건에 맞게 조정하는 것을 피하고 싶습니다.

편집하다: 엄격하게 최적의 솔루션을 찾을 필요는 없습니다. 명단은 현재 매뉴얼이 완료되었으며, 결과는 대부분의 시간에 상당히 차선책이 될 것이라고 확신합니다. 단기 조정 및 수동 재정의 분명도도 확실히 필요하지만, 이것이 문제가 될 것이라고 생각하지 않습니다. 과거 및 수동 할당을 "고정"로 표시하면 솔루션 공간을 줄임으로써 실제로 작업을 단순화해야합니다.

도움이 되었습니까?

해결책

이것은 잘 해결하기 어려운 문제입니다. 이 주제에 대해 특히 운영 연구 필드 - 예를 들어 참조하십시오 간호사 명단 논문 2007-2008 또는 Google "간호사 명단 작업 연구". 복잡성은 또한 다음과 같은 측면에 달려 있습니다. 해결해야 할 며칠; 간호사의 "요청"유형; 명단은 "순환"입니다. 장기 계획입니까 아니면 질병 및 스왑 등과 같은 단기 명단 "수리"를 처리해야합니까?

설명하는 알고리즘은 a입니다 휴리스틱 접근하다. 문제의 특정 사례에 대해 잘 작동하도록 조정할 수 있지만 "무언가"가 변경 되 자마자 잘 작동하지 않을 수 있습니다 (예 : 지역 최적, 수렴 불량).

그러나 이러한 접근 방식은 특정 비즈니스 요구에 따라 적절할 수 있습니다. 예를 들어 최적 솔루션은 동일하게 유지할 것으로 예상되는 문제 개요, 잠재적 인 저축 (돈과 자원), 간호사의 명단의 품질에 대한 인식,이 작업의 예산은 얼마입니까?

다른 팁

음, 일부 ILP-Solvers가 꽤 좋은 일을한다는 것을 알고 있습니까? AIMMS, Mathematica 또는 GNU 프로그래밍 키트를 사용해보십시오! 600 변수는 물론 Lenstra 정리가 쉽게 해결되는 것보다 훨씬 더 많지만 때로는이 ILP 솔버가 양호한 손잡이가 있고 AIMM에서 분기 전략을 약간 수정할 수 있습니다. 또한 ILPS에 대해 100%급식이 매우 빠릅니다.

최근 대형 제조 공장의 교대 할당 문제를 해결했습니다. 먼저 우리는 순전히 임의의 일정을 생성하고 통과 한 일정을 반환했습니다. is_schedule_valid 테스트 - 폴백 알고리즘. 물론 이것은 느리고 불확실했습니다.

다음으로 우리는 유전자 알고리즘을 시도했지만 (제안한대로) 유전자 알고리즘을 시도했지만 실행 가능한 솔루션에서 닫힌 좋은 피트니스 기능을 찾을 수 없었습니다 (가장 작은 변화는 전체 일정을 옳고 그름으로 만들 수 있기 때문에 거의 포인트가 없기 때문입니다).

마지막으로 우리는 다음 방법을 선택했습니다 (훌륭하게 작동했습니다!).

  1. 입력 세트 (예 : 작업, 시프트, 직원 등)를 무작위 화하십시오.
  2. 유효한 튜플을 만들어 잠정적 일정에 추가하십시오.
  3. 유효한 튜플을 만들 수 없으면 마지막 튜플이 추가 된 롤백 (및 증분).
  4. 부분 일정을 테스트하는 함수로 전달하십시오 could_schedule_be_valid, 즉, 나머지 튜플이 가능한 방식으로 채워지면이 일정이 유효 할 수 있습니다.
  5. 만약에 !could_schedule_be_valid, 간단히 롤백 (및 증분) (2)에 추가 된 튜플.
  6. 만약에 schedule_is_complete, return schedule
  7. GOTO (2)

이 방법으로 부분적인 이동을 점진적으로 구축합니다. 이점은 유효한 일정에 대한 일부 테스트는 2 단계 (사전 테스트)에서 쉽게 수행 할 수 있고 다른 테스트는 5 단계 (사후 테스트)에 남아 있어야한다는 것입니다.

행운을 빕니다. 우리는 첫 두 알고리즘을 시도했지만 며칠을 낭비했지만 5 시간 미만의 개발에서 유효한 일정을 즉시 생성하는 권장 알고리즘을 얻었습니다.

또한, 우리는 알고리즘이 존중할 과제의 사전 고정 및 포스트 고정을 지원했습니다. 1 단계에서 해당 슬롯을 무작위로 무작위 화하지 않습니다. 솔루션이 최적의 어느 곳에서나있을 필요는 없습니다. 우리의 솔루션은 최소 O (N*M)이지만 전체 제조 공장의 경우 0.5 초 이내에 PHP (!)에서 실행됩니다. 아름다움은 좋은 일정을 빨리 사용하여 좋은 일정을 배제하는 것입니다. could_schedule_be_valid 테스트.

그것을하는 데 익숙한 사람들은 수동으로 한 시간이 걸리더라도 상관하지 않습니다. 그들은 더 이상 수동으로 할 필요가 없다는 것을 알고 있습니다.

마이크,

당신이 이것에 대한 좋은 답변을 얻었는지 모르겠지만, 제약 조건 프로그래밍이 티켓이라고 확신합니다. GA가 답변을 줄 수 있지만 CP는 많은 답변을 제공하거나 실행 가능한 솔루션이 없는지 알려주도록 설계되었습니다. "제약 프로그래밍"및 스케줄링에 대한 검색은 많은 정보를 가져와야합니다. 비교적 새로운 영역이며 CP 방법은 전통적인 최적화 방법이 쇠약 해지는 많은 유형의 문제에서 잘 작동합니다.

동적 프로그래밍 라 벨? 겹치는 장소가있는 것처럼 들린다 : 겹치는 하위 문제, 최적의 하위 구조.

당신이 할 수있는 한 가지는 문제에서 대칭을 찾는 것입니다. 예를 들어 모든 간호사를 문제의 목적에 따라 동등한 것으로 취급 할 수 있습니까? 그렇다면 간호사는 임의의 순서로만 간호사를 고려하면됩니다. 간호사가있는 해결책을 고려하지 않아도됩니다. 나 간호사 앞에서 예정되어 있습니다 제이 어디 나 > 제이. (당신은 개별 간호사가 교대 시간을 선호했다고 말했는데,이 예는 아마도 덜 중요한 목표이지만이 예와 모순 되는가?)

유전자 알고리즘을 사용해야한다고 생각합니다.

  • 큰 문제 인스턴스에 가장 적합합니다.
  • 그것은 부정확 한 답변의 가격에 대한 시간 복잡성을 줄입니다 (궁극적 인 최고가 아님)
  • MEN이 아닌 사람에 대한 체력 처벌을 조정하여 제약 및 선호도를 쉽게 지정할 수 있습니다.
  • 프로그램 실행에 대한 시간 제한을 지정할 수 있습니다.

  • 솔루션의 품질은 프로그램을 해결하는 데 얼마나 많은 시간을 보내려고하는지에 달려 있습니다 ..

    유전자 알고리즘 정의

    유전자 알고리즘 튜토리얼

    GA를 통한 클래스 일정 프로젝트

또한 다음을 살펴보십시오.비슷한 질문 그리고 다른 것

CSP 프로그래밍을 사용하여 자동 Shitfs 명단을위한 프로그램을 만들었습니다. 예 :

  1. 2 교정 시스템 - 100 명 이상의 간호사, 30 일 시간의 시간, 10 개 이상의 규칙 테스트
  2. 3 교 변화 시스템 - 80 명 이상의 간호사, 30 일 시간의 시간, 10 개 이상의 규칙 테스트
  3. 3- 교대 시스템, 4 팀-365 일의 수평선, 10 개 이상의 규칙 테스트,

그리고 두 개의 비슷한 시스템. 그들 모두는 내 가정용 PC (1.8GHz, 듀얼 코어)에서 테스트되었습니다. 실행 시간은 항상 허용되었습니다. 3/ 300MB RAM이 걸렸습니다.

이 문제의 가장 어려운 부분은 적절한 솔버와 적절한 해결 전략을 선택하는 것이 었습니다.

Metaheuristics 아주 잘했습니다 국제 간호사 명단 경쟁 2010.

구현하려면 이것을 참조하십시오 연속 간호사 명단 (Java)이있는 비디오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top