# Resource scheduling problem with synchronization constraints: Weak LP relaxation

I have a resource assignment/scheduling problem which involves assigning jobs to $$m$$ workers. There are 2 sets of different jobs, $$J^1$$ and $$J^2$$, and a set of periods $$T$$.

• Let $$d_{jt}$$ be the number of workers required to perform job $$j\in J^1$$ in period $$t\in T$$.
• A job $$j\in J^2$$ requires $$d_j$$ workers, and can be started at any one period $$B_j\subset T$$. Once started, $$j$$ cannot be preempted, and must be performed by the same $$d_j$$ workers from beginning to the end. The duration of a job $$j\in J^2$$ is given by $$dur(j)$$.

Let $$S$$ be the (exponentially large) set of all different worker schedules. Binary parameter $$a_{sjt}$$ indicates whether job $$j\in J^1$$ is worked on in period $$t\in T$$ in schedule $$s\in S$$ . Similarly, binary parameter $$b_{sjt}$$ indicates whether job $$j\in J^2$$ is started in schedule $$s$$ in period $$t$$.

We can now formulate the problem as follows. Let $$\lambda_s$$ indicate whether schedule $$s\in S$$ is selected, $$y_{jt}$$ the shortage of workers for $$j\in J^1$$ in period $$t$$. Variable $$z_{jt}$$ indicates whether $$j\in J^2$$ is started in period $$t$$, and $$y_j$$ indicates whether $$j\in J^2$$ isn't started in any period.

\begin{align} \label{eq:m.1}\mbox{minimize }& \sum_{s\in S}c_s\lambda_s + \sum_{j\in J^1}\sum_{t\in T}p_jy_{jt}+\sum_{j\in J^2}p_jy_j &\\ \label{eq:m.2}\mbox{s.t. }&\sum_{s\in S}\lambda_s \leq m & \\ \label{eq:m.3}& \sum_{s\in S}a_{sjt}\lambda_s + y_{jt} \geq d_{jt} & \forall j\in J^1,t\in T \\ \label{eq:m.4}&\sum_{s\in S}b_{sjt}\lambda_s \geq d_j z_{jt} & \forall j\in J^2, t\in B_j\\ \label{eq:m.5}&\sum_{t\in B_j}z_{jt} + y_j = 1 & \forall j\in J^2\\ \label{eq:m.6}&\lambda_s\in \{0,1\} &\forall s\in S\\ \label{eq:m.7}&y_{jt} \geq 0 & \forall j\in J^1, t\in T\\ \label{eq:m.8}&z_{jt}\in \{0,1\} & \forall j\in J^2, t\in B_j\\ \label{eq:m.9}&y_j\geq 0 & \forall j\in J^2 \end{align}

The objective minimizes the cost of the schedules, the worker shortage for jobs in $$J^1$$ and the number of unperformed jobs in $$J^2$$ (weighted by a penalty). At most $$m$$ schedules can be selected (Constr 1). Constr 2 ensure that every period sufficient workers are assigned to each job in $$J^1$$. Constr 3 ensures that a job in $$J^2$$ can only be started if sufficient workers are present. Constr 4 links $$z_{jt}$$ and $$y_j$$: $$y_j=1$$ iff $$j\in J^2$$ is not started.

I'd like to solve the above problem through Column Generation. The real problem I'm trying to solve is significantly more complex. Due to the usage of a set of schedules $$S$$, part of this complexity is hidden away. E.g. there are all sorts of legal, and operational constraints that define a 'feasible' schedule, involving breaks, working hours, worker skills, etc. Hence it would be highly desirable to generate schedules in a pricing problem as opposed to adding all these constraints to a huge ILP.

The problem is that the LP relaxation of the above formulation is quite weak. Any ideas on how to strengthen it, perhaps with valid inequalities or some changes in the formulation?

Example problem instance:

• $$T=\{1,2,3,4,5\}$$, $$m=2$$ workers
• $$J^1=\{1,2\}$$, $$d_{11}=d_{24}=d_{25}=1$$ (other $$d_{jt}$$ parameters are 0).
• $$J^2=\{3\}$$, $$d_3=2$$, $$B_3=\{1,2\}$$, dur(3)=3

Possible feasible solution:

S/T 1 2 3 4 5
$$s_1$$ $$3$$ $$3$$ $$3$$ $$2$$ $$-$$
$$s_2$$ $$3$$ $$3$$ $$3$$ $$-$$ $$2$$

The table indicates which job is performed in schedule $$s_i$$ in period $$t$$, e.g. job $$2$$ is performed in period 4 in schedule $$s_1$$. An $$-$$ indicates idle. In this solution $$y_{11}=1$$, $$y_3=0$$, $$z_{31}=1$$ and the objective value: $$c_{s_1}+c_{s_2}+p_1$$. Note that no schedule exists where no penalty is incurred. Here's what the LP relaxation would look like:

S/T 1 2 3 4 5
$$s_1$$ $$3$$ $$3$$ $$3$$ $$2$$ $$-$$
$$s_2$$ $$1$$ $$3$$ $$3$$ $$3$$ $$2$$

Here $$y_{11}=0$$, $$y_3=0$$, $$z_{31}=z_{32}=\frac{1}{2}$$, and the objective value $$c_{s_1}+c_{s_2}$$. Notice that the start of job 3 is no longer synchronized across the 2 schedules.

• Is there an assumption that all schedules are busy at all times? Basically what I'm asking is whether, for every schedule $s$ and every time $t$, either $a_{sjt}=1$ for some $j\in J^1$ or $b_{sj\tau}=1$ for some $j \in J^2$ and some $\tau \le t$ such that starting job $j$ at time $\tau$ implies job $j$ is still going at time $t$?
– prubin
Jul 30, 2021 at 20:10
• @prubin: no there's no such assumption. There's a special 'idle' job (which is not part of $J^1$ or $J^2$). The idle job represents breaks, and 'do-nothing'. An example is given for schedule $s_2$ above where the worker does not work on any job in period 4, i.e. the worker is idle. So in every schedule s, and period t, a worker is either idle, or is busy performing a job in $J^1$ or $J^2$. Jul 30, 2021 at 21:02