Scheduling Medical Residents

Classical Scheduling

The data for a simple classical scheduling problem include:

• a partial order \(\leq\) on tasks,
• a function \(c : T \rightarrow C\) from tasks to cost vectors, and
• a distinguished cost vector, \(R : C\) called the resource constraint.

A solution \(f : T \rightarrow 2^E\) is an assignment of tasks to sets of episodes such that the solution is:

• faithful: \(t_1 \leq t_2 \implies \forall e_1 \in f\,(t_1), \forall e_2 \in f\,(t_2), e_1 < e_2\)

• costful: \(\forall e \sum\limits_{t \in f^{-1}(e)} c\,(t) \leq R\) elementwise, and

• adequate: \(\forall t \sum\limits_{e \in f(t)} e = c\,(t)\)

A good solution also minimizes some loss function \(L\), like “total duration”.