1
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 21, 2023 at 16:01

4 Answers 4

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$
0
$\begingroup$

This thread is already a year old, but let me add a comment anyways.

The machine minimization problem is actually quite well studied, but some interesting open problems remain.

The problem: There is given a set of jobs where each job j has a processing time p_j, a release date r_j, and a deadline d_j. In a feasible schedule, any job j must be assigned to machines for p_j units of time during the time window [r_j,d_j), possibly being preempted and possibly migrating over several machines. However, no job can be running on several machines at the same time and each machine can be processing only one job at a time. The task is to determine a minimum number of machines that has to be available such that there is a feasible schedule.

This problem is known to be solvable optimally in polynomial time via linear programming or maximum flow computations [1].

For a given number of machines, the natural linear programming (LP) formulation gives a fractional assignment of workload to time slots. This can be rounded in a straightforward way by assigning the fractional workload in a round robin fashion over all machines within a time unit. The minimum number of machines can be found by binary search.

The problem complexity changes when preemption is not allowed. The non-preemptive version is NP-hard. It is already NP-hard to decide whether a given set of jobs can be feasibly scheduled without preemption on a single machine; see Garey and Johnson. There are known only non-constant approximations within polytime [2]. It is an interesting open question whether a constant-factor approximation algorithm exists.

Under online job arrivals, also the preemptive problem gets drastically harder. There has also been some research, see [3] and follow up papers. It is a major open problem whether a constant-competitive online algorithm exists.

[1] W. A. Horn, Some simple scheduling algorithms, Naval Res. Logist. Q., 21 (1974), pp. 177--185.

[2] Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90

[3] L. Chen, N. Megow, K. Schewior, An O(log m)-Competitive Algorithm for Online Machine Minimization, SIAM Journal on Computing 47(6), 2057–2077, 2018.

$\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.