Definition of a modified scheduling problem where jobs are halted based on the shifts of employees

Question

I am looking for the name of a scheduling problem in literature with some references. Here is the variant that I have in mind.

Given a set of jobs, employees have certain shifts that they can work on these jobs. Suppose employee $e$ starts processing job $j$ on machine $m$, but before completing the job, his shift finishes. The rule is that no other job can replace $j$ until its process is completed. That is why either the same employee or another employee should come and continue working on $j$ based on their shift requirements.

I was wondering how this problem is defined / called and if there are efficient formulation proposed for it in the literature. I am aware of the preemptive scheduling, but my problem definition is a little bit different than it.

Answer 1

The closest topic of what you described that I am aware of is the field of "Scheduling with machine availability constraints". In particular, the semiresumable case:

Under the semiresumable assumption, the disrupted operation will have to partially restart after the machine becomes available again

Here is a not so recent survey of these problems:

• "A survey of scheduling with deterministic machine availability constraints" (Ma et al, 2010) DOI

Answer 2

As you pointed out this is not a case that preemption would help. The preemptive constraint is often used where we are still allowed to split a job/task if another job/task with higher priority needs to be processed on the same machine/resource. In this case, the on-hand processed task would be stopped or moved to another machine/resource (splitting the processing task) to process the new one with higher priority.

Now, I assume there are no other constraints on the problem you mentioned. The scheduling model you are having is a variant of the Parallel machine scheduling problem with the resourced constraints. $ \text{P}_{m} || \sum w_{j}c_{j} \ Or \ C_{max}$. Also, As far as I know, the problem is classified as NP-Hard in the Ordinary Sense$^1$.

The $ \text{P}_{m} || C_{max}$ can already be solved efficiently by applying LPT (The Longest Processing Time first) rule. Also, one of its practical forms in presence of the machine eligibility constraint would be LFJ/LFM (the Least Flexible Job/Machine first). Besides the mentioned algorithms it would be worth taking a look at MILP, CP, etc. to solve such a problem in an optimal sense.

To assign employees to the machines in each shift, either rough cut capacity planning (RCCP) or the simulation method would be useful. Please, be aware that it is still usual that at the end of each shift, some WIPs/jobs would be remaining or being under process till another operator comes to complete that. Such times are often called the chang-over time and can be assumed as planned stop time.

---

$^1$ - Scheduling Algorithms

Answer 3

It can be solved by mathematical optimization. I'd go by below:
Define variable $ x_{j,m}^t$ where $t$ represents the shift
If $D_j$ is the processing time for job $j$ & $ S_t$ is shift duration at $t$ then you need a constraint like
$ D_j \le Ux_{j,m}^{t+1} + \sum_{k\le t}x_{j,m}^kS_k$
and
$ \sum_{k\le t}x_{j,m}^kS_k - D_j \le U(1-x_{j,m}^{t+1})$
where binary variable $ x_{j,m}^t=1$ if job $j$ is assigned to machine $m$ at time $t$, else 0 and
$U$ is a large number, not too large just based on the scle of the model, could be upper bound of something like sum of all shift durations. Also
$ \sum_j x_{j,m}^t \le 1$: ensures one job per machine at a time