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 ...
- 37.8k
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 ...
- 30.4k
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 ...
- 136
4
votes
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 ...
- 12.9k
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 ...
- 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 (...
- 55
3
votes
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 ...
- 30.4k
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 ...
- 8,390
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 ...
- 1,461
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 ...
- 136
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.
- 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 ...
- 37.8k
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) ...
- 328
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/...
- 892
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 ...
- 8,390
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}$
$\...
- 3,343
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 ...
- 3,343
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 \ | \...
- 8,390
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$: $ ...
- 3,343
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 ...
- 1,198
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/...
- 509
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.
- 30.4k
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 ...
- 8,390
1
vote
How to tackle online scheduling problems?
Take a look into Real-time planning and Non-disruptive replanning. See my video.
- 4,717
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&...
- 37.8k
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 ...
- 37.8k
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 ...
- 8,390
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 ...
- 2,587
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 ...
- 11.9k
Only top scored, non community-wiki answers of a minimum length are eligible