2
$\begingroup$

I am relatively new to the topic of optimization. I am currently trying to address the following problem:

We are given a set of jobs, say $J$ with release times, deadlines and duration. Jobs can be pre-empted and also can be scheduled to run in parallel on different machines with the only constraint that a unit of a given job (from its duration) cannot be proccessed at the same time on 2 different machines. Objective is to find the minimum amount of machines required for a feasible schedule to be possible (not the schedule itself).

I am seeking a polynomial time solution. Is someone aware of such problem in the literature?

$\endgroup$
5
  • $\begingroup$ Is there a reason why you are seeking a polynomial time solution? As @fontanf notes, the existence of one is unlikely. Also, "polynomial time" does not equate to "fast". If a polynomial time solution existed, it could turn out to take longer than, say, solving a reasonably tight MIP model. $\endgroup$
    – prubin
    Feb 19, 2023 at 19:40
  • $\begingroup$ @prubin I was seeking a fast approach as I am going to be using it as part of a two-stage method. I will be happy to consider a MIP model as well. $\endgroup$
    – Pia MiA
    Feb 20, 2023 at 18:59
  • 1
    $\begingroup$ @PiaMiA, would you please, elaborate more on the problem specification. What exactly you mean by the minimum amount of machines required? If you have the parallel resources to assign jobs, why not try to optimize e.g. completion time in which maximizing the resources utilization? Also, as you did not say anything's about the resources available time, it can be possible to assign jobs to only one resource, but with the longer completion time in contrast to using multiple resources. $\endgroup$
    – A.Omidi
    Feb 20, 2023 at 21:04
  • $\begingroup$ Can you clarify what you mean by a "unit of a given job". Are you saying that parts of the same job can be running simultaneously on different machines? $\endgroup$
    – prubin
    Feb 21, 2023 at 0:10
  • $\begingroup$ @prubin Each job has an integral duration. The job can be pre-empted at integral points but an integral unit cannot be scheduled at the same time on 2 different machines. I hope this makes it clearer. $\endgroup$
    – Pia MiA
    Feb 21, 2023 at 16:01

3 Answers 3

0
$\begingroup$

Assuming that there is no time cost for moving a job onto or off of a machine, you could try the following MIP model. The parameters (all assumed integer) are the set of jobs (indexed $j=1,\dots,J$), the time horizon (indexed $t=1,\dots,T$), and for each job $j$ the release time $r_j,$ the deadline $d_j$ and the duration $\delta_j.$

There are binary variables $x_{j,t}$ signalling whether job $j$ is running at time $t$ (with $x_{j,t} = 0$ for $t < r_j$ or $t > d_j$) and a continuous variable $y\ge 0$ measuring the number of machines needed.

The objective is to minimize $y.$ Constraints are as follows. $$\sum_{t=1}^T x_{j,t} = \delta_j \quad \forall j=1,\dots,J$$ (each job must receive the necessary processing between its release and deadline dates) and $$y\ge \sum_{j=1}^J x_{j,t}\quad \forall t=1,\dots,T$$ (in each period there must be at least as many machines available as there are jobs being processed).

I would not be surprised if this model solved fairly quickly.

$\endgroup$
2
$\begingroup$

If the number of machines is fixed, determining if there is a feasible schedule under the conditions you described is NP-hard. Therefore, it's unlikely that there exists a polynomial exact algorithm.

I'm not aware of many polynomial algorithms for scheduling problems with preemption in general in the literature.

At first glance, I would try a binary search on the number of machines, and use a greedy algorithm to search for a feasible schedule with a fixed number of machines.

The greedy algorithm could look like:

  • For each job $j$
    • For each machine $i$
    • Schedule as much as possible of $j$ on $i$
$\endgroup$
1
$\begingroup$

I solved a problem with objective to minimize resources. I have to agree that this problem is not addressed in literature.

This problem is generally more complicated than minimization of makespan for example since a solution with less resources can be very different compared to a solution with more resources.

In your case I would recommend to use constraint programming and use capacity of cumulative constraint (if possible) to express needed resources. Classical constraint solver can be trapped in local optimum, better is to use cp-sat solver from ortools.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.