# How to formulate this scheduling problem efficiently?

Let there be $$N$$ users with individual demands (of some items). Some users can have higher demands while the others can have lower demands. There are exactly $$N$$ service points. There is a one-to-one mapping between the users and the service points. At any point in time, only $$P$$ persons can be served, i.e., only $$P$$ service points are activated. There are a total of $$M$$ time slots where one time slot is equal to one hour. The $$P$$ service points that are activated simultaneously must not be adjacent. A service point can deliver a given number of items in a time slot. So, a given user can be served during some of the time slots.

So, my formulation of the scheduling problem becomes

\begin{alignat}2\max \min&\quad \left\{\frac{s_1}{d_1},\frac{s_2}{d_2},\cdots,\frac{s_N}{d_N}\right\}\\\text{s.t.}&\quad s_n=\sum_{m=1}^MZ(n,m)q_n\\&\quad Z(:,m)^\top{\bf A} Z(:,m)=0\quad&\forall m\in\{1,2,\cdots,M\}\end{alignat}

Note that the objective, the first and second constraints are convex/linear.

The last constraint is binary quadratic, which is very difficult to solve. Of course we can express it in a different way and linearize it as proposed in How can I linearize or convexify this binary quadratic optimization problem?. With the values I have for $$N$$ and $$M$$, the number of resulting linear constraints from the linearization is huge.

Note: $$\bf A$$ is not a PSD. It has eigenvalues which are both positive and negative.

• Can you provide your formulation so far, and tell us specifically where you are getting stuck? Currently, your question reads as though you are asking us to formulate the whole problem from scratch, which I assume is not really what you are asking. See also How to ask for help with your model. Jul 9, 2019 at 23:57
• @LarrySnyder610, I have provided my formulation. Please have a look. I am looking forward to an efficient formulation. Jul 10, 2019 at 7:21
• You can reformulate the last constraints: What you want to express is that for all timeslots $m=1,\ldots,M$ two adjacent service points cannot be open. This can be achived by $\forall p_1, p_2\in A\,\forall m: Z(p_1,m) + Z(p_2,m) \leq 1$. Note we only need this for all pairs of adjacent service points, hence slightly abusing notation. Jul 10, 2019 at 11:04
• @dipaknarayanan Note that if you @-tag someone in a comment, they are not notified unless they have already commented on the same thread. So you can't "ping" someone to a new post just by @-tagging them -- setting aside the etiquette of calling out someone to ask them to answer your question, which in my opinion might also be a little iffy. Jul 10, 2019 at 13:36

I would rephrase the model a bit not using OP's matrix formulation. Instead of a matrix I will use binary variables $$z_{st}$$ indicating whether a service point $$s$$ is active in time slot $$t$$. Using the same two constraints and reformulating the $$\min$$ in the objective function and the last constraint to be linear we arrive at the following model: $$\begin{array}{ll} \text{maximize} & v \\ \text{subject to}& \forall m=1,\ldots,M: \sum\limits_{n=1}^N z_{nm} \leq P \\ &\forall n=1,\ldots,N: s_n = \sum\limits_{m=1}^M z_{nm}q_n \\ &\forall n=1,\ldots,N: v \leq \dfrac{1}{d_n}s_n\\ &\forall m=1,\ldots,M \,\forall (n_1, n_2)\in A \text{ where } A_{n_1 n_2}=1: z_{n_1m} + z_{n_2m} \leq 1\\ &\forall m=1,\ldots,M \,\forall n=1,\ldots,N: z_{nm} \in \{0,1\} \end{array}$$