[Optimization] 5. LP Model (4) Scheduling Models

[Ref] Optimization in Operations Research, Rardin

​

안녕하세요. 이번 포스팅에서 공부해볼 LP 모델은 Scheduling Model 입니다.

제가 생각하기에, Scheduling Model이 저희가 일상생활에서 가장 자주 접할 수 있는 최적화 문제인 것 같아요.

​

Scheduling Model로써 굉장히 유명한 예시를 공부해봅시다.

바로, 슈퍼마켓 근무 시간표 작성 문제입니다.

슈퍼마켓은 일반적으로, 낮 시간에는 한가하지만, 18시 이후에는 굉장히 바빠집니다.

따라서, 효율적인 스케쥴링이 굉장히 중요한 문제입니다.

근무에는 full time 근무자와, part time 근무자 두 종류가 존재합니다.

슈퍼마켓의 근무에 할당량이 있는데, full-time 근무자가 part-time 근무자보다 더 많은 일을 할 수 있습니다.

근무자의 종류에 따라, 시급이 달라지며, 그리고, 18시 이전과 이후의 시급이 다릅니다.

마지막으로, 추가 근무시 시급의 150%가 지불되야 하지요.

이 때 물론 제약조건이 있습니다.

절반 이상의 full-time 근무자가 추가 근무를 하면 안됩니다. (노동법1)

그리고 추가 근무시간이 하루에 20시간이 넘으면 안되요. (노동법2)

마지막으로, 각 시간마다 슈퍼마켓 업무에 할당량이 존재한다는 것이지요.

​

일단 전체 근무자가 35명이라고 가정을 할 때, 목적함수는 위와 같이 정의됩니다.

추가적인 제약조건은 위와 같이 정의됩니다.

​