Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule.
That said, I have a few questions regarding the process. I haven't worked with linear programming before, but the math isn't the concern. It's expressing the constraints.
Let me describe them:
I have several roles to fill. Role A, say, is a priority, then each role after that is less important. I then have several groups of individuals. Group A can perform tasks in role A, and any other tasks after that. Then Group B, can't fill Role A, but any task after that. Each group, from increasing alphabetical order, has less individuals then the previous (i.e. A
That is the general idea.
Like I said before, I don't have much experience with linear programming (I recently ordered a book on the subject, but if there are any good suggestions that deal with applications like the above would be very much appreciated).
In any case, I'm particularly curious as how the constraints would look regarding having several roles with priorities that only certain groups can perform. Obviously, it's quite simple to write a constraint stating that each role must be filled, but I haven't seen many constraints describing what I'm needing.
Also, I'm still trying to find a way to express each group. For instance, say group A was composed of {Ed, Ted, Red, Bob, John}. Would I express that group as a variable itself, such as x? However, that violates one of the needed constraints: Ed can't have two roles at the same time! I need a way to prevent that. A matrix within a matrix perhaps? So A=[Ed, Ted,…]. It would more likely be a column matrix though.
Regardless, a little insight would be helpful. I don't necessarily want a complete answer, such as do this then this – more so a good starting place.
Any help is appreciated.
Best Answer
This problem won't strictly be a linear program, but is better suited to Integer Programming.
First question: What sort of sets are working with? We seem to have a set of jobs that must be completed. Additionally, we have a set of people who can do these jobs. Let's denote these sets $J$ and $P$, respectively. I'll assume those are the only sets you're dealing with, unless you'd like to clarify further.
Next question: What sort of decision variables will I need to formulate the problem? Well, we probably need to assign people to jobs, in some fashion. Let $j\in J$ and $p\in P$ and let \begin{equation*}x_{ij}=\begin{cases}1& \text{job } j \text{ is completed by person }p\\ 0& \text{otherwise}\end{cases}.\end{equation*} Alternatively, you might want to assign a person to a group, the A and B you spoke of, or a group and a job, etc. You'll have to go back and make more sets, if that's the case.
What sort of parameters do you need? Maybe something that measures your utility of finishing one job before another? Then, you would need a parameter $v$ which encodes a value for each job.
What's your goal? Receive the most utility from completing these jobs? Complete as many as possible? etc. Encode whatever your objective is into a function using whatever sets, variables, and parameters you've defined above.
What constraints do you need? A common constraint in such a resource allocation problem might be that a person can only work on a finite number of jobs throughout the week, say $c$. We might write this constraint as \begin{equation*} \sum_{j\in J} x_{jp}\leq c \hspace{10pt}\forall p\in P. \end{equation*}
The above info is a great general approach to formulating math programming problems.
As for your question regarding forbidding specific tasks from people who are in particular roles, let's suppose we have a set of roles $R$, jobs $J$, and people $P$. Consider $y_{rp}$, a decision variable equal to 1 if person $p$ is assigned to role $r$, and $x_{jp}$ from above. Further, let $J_r\subseteq J$ be a portion of the jobs only a member of role $r$ can perform. Then, we might write the constraint \begin{equation*} \sum_{j\in J'} x_{jp}\leq cy_{rp} \hspace{10pt}\forall p\in P. \end{equation*}
Note that if person $p$ is not assigned to role $r$, he cannot perform any of these tasks, as \begin{equation*} \sum_{j\in J_r} x_{jp}\leq 0. \end{equation*}
However, if he is assigned to role $r$, he may perform as many as $c$ tasks from subset $J_r$.
Does that help get you started? Feel free to ask other questions...