Skip to main content
10 votes

What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?

CP is not a subset of MILP. They are separate modeling/solving paradigms whose domains of application overlap. Both can solve for optimal solutions (in CP's case, by incorporating a constraint that ...
prubin's user avatar
  • 39.3k
6 votes
Accepted

Model generation for large-sized instances

I suggest three major changes: Omit the $y$ variables. Replace the $a_{p,j,t,i}$ variables with $a_{p,j,t,i,n}$. Instead of pairs of jobs, consider much larger subsets of jobs. The resulting ...
RobPratt's user avatar
  • 32.3k
4 votes
Accepted

Use of variance in job ordering

Just two disclaimers to start with: I'm not using it presently. Due to this sentence and the lack of broader context in your question (e.g., if there are any other stochastic variables in your model ...
Tim Varelmann's user avatar
4 votes

opposite of no_overlap constraint in docplex for CP

You can use overlap_length ...
Alex Fleischer's user avatar
4 votes
Accepted

Python Pulp - LpMinimize Not Returning Expected Output - Scheduling Problem

First, it is confusing when you say The final solution does not satisfy the workforce requirements for the various time windows, it's substantially short. Only 5 shifts are filled in total. You do ...
Kuifje's user avatar
  • 13.5k
3 votes

What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?

Google has a very nice library called OR Tools. One of those tools is a CP-SAT solver. Even though their solver works only on integer valued variables it is not that hard to convert MILP models to ...
berkorbay's user avatar
  • 341
3 votes

How to identify constraints that make problem not solvable in polynomial time?

You can also see that the second part, constraints 13 to 16, contains more variables (IxI), more constraints (IxIxMxM) and a big M formulation (which is not good for MIP resolution). The first part (...
Issouf's user avatar
  • 65
3 votes
Accepted

How to identify constraints that make problem not solvable in polynomial time?

The motivation is the same as in the Jain and Grossmann reference [59]. After assigning jobs to machines, the problem decomposes into a separate feasibility subproblem for each machine. Jain and ...
RobPratt's user avatar
  • 32.3k
3 votes

Optimizing Storage Allocation and Supply for Manufacturing with Time Constraints

I guess, as you correctly mentioned, this problem is too complex as actually many of the SCM problems are complex and I doubt one math formulation can handle all of its aspects. Instead, the problem ...
A.Omidi's user avatar
  • 8,950
2 votes

Python Pulp - LpMinimize Not Returning Expected Output - Scheduling Problem

You expect $y_j > 0$ for every $j$. Looking at the LP however, this does not need to be the case. Just the sum $y_j * a_{jt}$ over every $j$ needs to fulfill your demand for every $t$ (i.e. be at ...
PeterD's user avatar
  • 1,636
2 votes

Assignment Problem with continuous decision variable

Is there even a possibility that the mathematical optimal solution is a continuous value I would say it depends on the parameterization, i.e., the values of c and t and b in your problem. From your ...
Tim Varelmann's user avatar
2 votes

Identifying problem: Assignment + Job Shop Scheduling

That is something like a Flow Shop Multi Machine, In Cplex CP Optimizer you will find the Job Shop Multi Machines scheduling (jsspmm examples) which is a more general case.
GGG's user avatar
  • 41
2 votes

Identifying problem: Assignment + Job Shop Scheduling

I don't know that this problem falls neatly into any job scheduling category, although I would not be shocked if there are papers in the literature solving something equivalent or very similar. Both ...
prubin's user avatar
  • 39.3k
2 votes
Accepted

How to calculate the duration of a task in each shift?

$h_1, h_2, h_3$ mean the duration time in each period, respectively? Output also including the start time variables? Ans: $h_1 = (480 - start) * b_1$ $h_2 = duration - h_1 - h_3$ $h_3 = (finish - 960) ...
ytsao's user avatar
  • 386
2 votes

Is this classed as a version of jobshop? How should it be approached?

It's definitely a job-shop variant. Usually we use the terms "release time" and "deadline". See the job characteristics list here: https://en.wikipedia.org/wiki/...
Brannon's user avatar
  • 900
2 votes
Accepted

What are the alternatives to front loading of jobs/tasks/projects?

In the scheduling literature, there are some concepts to define a sequence/schedule plan. Optimal, non-delay, active, and semi-active schedule. W.r.t this and how you would change a sequence into a ...
A.Omidi's user avatar
  • 8,950
2 votes
Accepted

Efficient formulation of flexible job-shop scheduling constraints

Whether you need to index on time depends on what you are trying to achieve, what's your objective. If you are trying to work on constraints involving $a_{lm} $ then $ \sum_l l\delta_{lij} =t_{ij}$ $\...
Sutanu Majumdar's user avatar
2 votes
Accepted

Optimal to-do list scheduling in Python using Pyomo

In addition to the below code for m in model.Tasks: model.column_constraint.add(sum( model.x[n,m] * 0.25 for n in model.Intervals ) <= durations[m]) If you ...
Sutanu Majumdar's user avatar
2 votes

Problem similar to job shop

Based on What you mentioned, you could have a look at the parallel machine scheduling problem with precedence, resource capacity, and batch processing constraints. ($ P_{m} \ | \ cap, prec, batch \ | \...
A.Omidi's user avatar
  • 8,950
2 votes

Problem similar to job shop

Without knowing more details below is the outline what you can follow/develop further:\ Products: $P_p $: Priority $ Z_p$, Type$ C_c$, Processing time $ T_p$ Machines: Type: $ M_m$: Number $ N_m$: $ ...
Sutanu Majumdar's user avatar
2 votes
Accepted

Formulating a non-multitask constraint

First of all, I have to state that I do not know how to formulate your problem as an LP model. However, I do know how to make it through an IP model. Thus, I will proceed with this strategy. Problem ...
Matheus Diógenes Andrade's user avatar
1 vote
Accepted

How to formulate fleet Assignment Problem?

You may want to have the 2 primitive sets: CITY e.g. CHI MNN KC_ and PERIOD or event points e.g. P0600 P0630 P0700 etc. The nodes of the network will be the 2-tuples (i,p) or (CITY, PERIOD) The arcs/...
LINDO Systems's user avatar
1 vote
Accepted

Scheduling next shift such its not within X hours of previous shift

Suppose binary decision variable $x_i$ indicates whether shift $i$ is scheduled. If shifts $i$ and $j$ conflict, then impose a constraint $x_i+x_j\le 1$ to prevent scheduling both.
RobPratt's user avatar
  • 32.3k
1 vote

How to minimize number of machines required to serve tasks, and return the schedules for each machine?

The problem you are facing is a variant of parallel machine scheduling problems with some limitations like release time, due date, and also unknown identical machines. This problem can be modeled as a ...
A.Omidi's user avatar
  • 8,950
1 vote

How to tackle online scheduling problems?

Take a look into Real-time planning and Non-disruptive replanning. See my video.
Geoffrey De Smet's user avatar
1 vote
Accepted

How to tackle online scheduling problems?

Disclaimer: I'm not a practitioner, so I don't know if any of the relevant academic literature is actually, well, relevant. That said, I think you might want to look at work on "rolling horizon&...
prubin's user avatar
  • 39.3k
1 vote
Accepted

Solver for Flexible Job Shop Scheduling Problem

There are constraint programming solvers that support global constraints specific to job scheduling (setup times, resource sharing etc.). CPOptimizer is the one with which I am most familiar, but I am ...
prubin's user avatar
  • 39.3k
1 vote

Efficient formulation of flexible job-shop scheduling constraints

Job shop scheduling problem is NP-hard in its essence and finding or developing a straightforward formulation to solve the large instance is really challenging work. If you would like to develop a ...
A.Omidi's user avatar
  • 8,950
1 vote

or-tools: job shop problem never exists not finding additional solutions

Proving optimality is where the NP-Hard part is. A lot of small job-shops are still open (meaning not proven). In your case, you have a maximization objective. You have found a feasible value with ...
Laurent Perron's user avatar
1 vote
Accepted

MIP gives out zero as best solution when trying to optimize MIP model for flexible job-hop

Although we would need to see your model to really be able to tell what's happening, as a new practitioner here's a few things that you might find helpful: First, zero can be a perfectly legitimate ...
Nikos Kazazakis's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible