반죽이 오븐을 기다리지 않으면 세 작업이 더 빨리 끝날까요? 교사는 혼합·굽기 두 단계의 종이 작업카드를 만들어요. A의 시간은 (3,8), B는 (7,2), C는 (4,5)분이에요. 실제 조리법의 시간은 아니에요.
혼합기와 오븐은 하나씩이며 각각 한 작업만 처리해요. 두 장비의 순서는 같고 세 카드를 한 번씩 써요. 시각0 이후 실수 시각에 시작하며 작업을 중단하지 않아요. 다른 카드끼리 혼합과 굽기는 겹쳐도 되고, 장비를 비워 두어도 돼요. 마지막 굽기의 종료를 T라 해 볼까요?
단계 사이 대기를 허용하면 혼합을 A·C·B 순서로 0·3·7에 시작하고, 굽기를 3·11·16에 시작하여 18분에 끝내요. 첫 굽기 전 최소3분과 굽기 합15분이 필요하므로 더 짧을 수 없어요. 18분의 모든 혼합 시작은 다음과 같아요.
굽기는 3·11·16으로 고정돼요. 순서 A·B·C는 C의 혼합 완료가 최소14라 19분 이상이고, 다른 첫 카드는 첫 굽기부터 늦어요. 위 영역은 혼합의 비겹침과 굽기 전에 준비됨을 모두 만족해요.
대기를 금지하면 혼합 직후 굽는다. 카드 i의 두 시간을 p_i,q_i, 혼합 시작을 s_i라 쓸게요. 연속한 i,j의 두 장비가 겹치지 않을 조건은
각 순서에서 이 간격을 합하면 최단 T는 ABC·ACB·BAC·BCA·CAB·CBA에 대해 20·20·23·24·19·22입니다. 대기 금지의 시작 시각은 C·A·B가 0·6·10입니다. 혼합기를 잠시 비우면서 오븐에서는 4~9·9~17·17~19를 써요. 금지 조건은 허용 일정을 줄이므로, 한 카드의 대기를 없앴다고 전체도 빨라지는 것은 아니에요.
착안: 캐나다 곡물위원회 CSP. 두 단계·시간·조건은 자체 모형이에요.