M.S.28 [OR-Tools 스터디] Employee Scheduling 다교대 시스템으로 일하는 고용자들이 있는 조직들에서는 매일 충분한 노동자들이 schedule될 필요가 있다. 전형적으로, schedule은 "직원들은 행으로 2교대로 일하면 안된다"와 같은 제약들을 가지고 있다. 모든 제약조건들을 만족하는 schedule을 찾는 것은 계산적으로 어려울 수 있다. 따르는 섹션에서는 직원 scheduling 문제의 두가지 예시를 보여주고, CP-SAT solver를 사용하여 그것들을 어떻게 해결할 것인지를 보여준다. A nurse scheduling problem 다음 예제에서는 병원 관리인들이 3일 동안 4명의 간호사들의 일정을 짜야할 필요가 있다. 그들은 다음의 조건들을 따른다. 각 하루를 8시간씩 3파트로 나눈다 매일 모든 교대는 한명의 간호사에게 할당되며, 어떠한 간.. 2023. 2. 25. [OR-Tools] Scheduling Overview 특정 시간에 일에 사람들과 자원들을 할당하기 위해 방대한 계산을 다루는 회사들은 규칙적인 기초에 기반하여 어려운 스케줄링 문제를 풀 필요가 있다. 여기에 그러한 문제들의 몇가지 예제가 있다. 복잡한 제약조건과 인원 배치 요구사항에 따라 직원을 여러 교대로 배치한다. 한번에 한가지 task만 수행하도록 제한된 기계들에 많은 task들이 수행되어야하는 것에 대한 생산 과정 조정 OR-Tool들은 이러한 것들과 같은 문제를 푸는 것에 있어서 강력한 기술을 제공해준다. 이후 따르는 섹션들에서는 몇가지 scheduling 문제들과 그것들에 대한 해결책들을 기술한다. Employee scheduling The job shop problem Reference: https://developers.google.com/o.. 2023. 2. 24. [OR-Tools 스터디] The Bin Packing Problem multiple knapsack 문제와 같이, bin packing 문제 또한 사물들을 bin에 포장하는 것도 포함된다. 그러나 bin packing문제는 다른 목적을 가지고 있다 : 모든 사물들을 넣을 수 있는 가장 최소의 bin 갯수를 찾는 것이다. 두 문제 간의 차이를 요약한 것이다 : Multiple knapsack problem : 다양한 용량들로 이루어진 bin의 고정된 갯수들에 사물들의 일부를 포장한다. 따라서 포장된 사물들의 전체 값은 최대화되어야 한다. Bin packing problem : 필수적인 공통의 용량들을 가진 많은 bin들이 제공되었을 때, 모든 사물들을 담을 수 있는 최소한의 갯수를 찾는 것이다. 이 문제에서 사물들은 부여된 값이 없다. 왜냐 ? 목적이 값을 얻는 것은 아니.. 2023. 2. 24. [OR-Tools 스터디] Solving a Multiple Knapsacks Problem 이 섹션에서는 MIP solver와 CP-SAT solver를 사용하여 multiple knapsack에 대한 knapsack problem을 어떻게 푸는지에 대해 보여준다. 이 경우, knapsack보다는 bin이라고 containter를 지칭하는 것이 더 흔하다. 다음의 예제는 다섯개의 bin들에 사물들을 포장하는 최적의 방법을 어떻게 찾는지를 보여준다. Example 이전의 예제와 마찬가지로, 다양한 무게와 값들에 대한 사물의 집합으로 시작한다. 이 문제에서는 사물들을 부분집합으로 5개의 bin들에 포장하는 문제이며, 이들 각각의 최대 용량은 100이고, 전체 포장된 값은 최대여야한다. 따르는 섹션에서는 이 문제를 푸는 프로그램을 보여준다. MIP Solution from ortools.linear.. 2023. 2. 24. 이전 1 2 3 4 5 6 7 다음