What type of scheduling problem is this?

Question

I'm trying to develop a heuristic to solve a scheduling problem. The difficult for me is to treat the time as a variable.

There are 2 variables related to time, $b_{ij}$ and $f_{ij}$, being the time that the machine j begin and end the job $i$ respectively. It's used like this because the model has a demand constraint (see below), that is attended with the time that the machines do job $i$, and each machine has a specific capacity ($q_j$). There is also in the model a binary variable $x_{ij}$ that says if the machine $j$ do the job $i$.

$$\sum_j \bigg((f_{ij} - b_{ij}) * q_j * x_{ij}\bigg) \geq Demand_i, \forall i$$

In this problem, all the jobs needs to be processed only one time by whatever machine.

If anyone knows which kind of scheduling problem it is... It'll be a great help.

Answer 1

I think it is similar to the Flexible Job Shop Scheduling Problem as one of the students in my research collaborators group discussed a similar model with me, while developing a customized MOEA for solving the multi-objective flexible job-shop scheduling problem (FJSP). Please refer to the following preprint and see if it is helpful for you:

Wang, Y., van Stein, B., Emmerich, M., & Bäck, T. (2020). A Tailored NSGA-III Instantiation for Flexible Job Shop Scheduling. arXiv preprint arXiv:2004.06564. [pdf]