3
$\begingroup$

I am doing research on optimizing a simple buffer allocation and need to run my model. I am new to this but someone told me about using Gurobi and I do not for the life of me know how to create the following LP model. Can someone please help me on the right path?

The situation is as follows:

  • There are 5 machines in the line each with a buffer in between in the form of:
  • b0 -> M1 -> b1 -> ... M5 -> b5, with M being the machines and b being the buffers.
  • b0 has a continuous flow of units into the line
  • b5 has an infinite capacity
  • The rest of the buffers have a finite capacity and is what needs to be optimized.
  • k is the max capacity per buffer
  • b_i (t) is the actual amount of units per buffer at moment t, at t=0 all buffers are empty.
  • v_i is the nominal production rate of the machine
  • th_i(t) is the number of units moved from b_(i-1) to b_i in step t.
  • The objective function is to maximize the sum of b_5, which is the sum of the actual amount of units in the last buffer.
  • t = 0, ..., 360
  • The speeds still need to be defined.

enter image description here

I am not an operations researcher in anyway, so this is all new and unfortunately I cannot post any producible sample or show how far I have come already, as I have nothing and don't totally understand it as of yet.

$\endgroup$
0

2 Answers 2

4
$\begingroup$

You correctly identified that this a linear program. You could either specify this problem in the .lp file format see the Gurobi documenation and consult the syntax rules if you have questions or you could use a modeling language like PuLP in Python or JuMP in Julia. I prefer JuMP as Julia makes it really easy to install open source solvers and also can talk to Gurobi (provided you have a Gurobi install). This problem is small enough that open source solvers will not be much slower then commercial solvers like Gurobi. So if Gurobi is not already installed i would recommend the Cbc solver which can be installed automatically by Julia. Below i will add the model transcribed to JuMP. You will just have install Julia and execute this command line.

using JuMP
using Gurobi

m = Model(Gurobi.Optimizer)

t = 360

@variable(m, 0 <= b[0:5,0:t])
@variable(m, 0 <= k[0:5])
@variable(m, th[0:5,0:t])
@variable(m, v[1:5,0:t])

@constraint(m, b[5,0:t] .<= th[5,0:t])

for tt in 1:t # can't constrain b[5,0] that way
  @constraint(m, b[5, tt] <= b[4, tt-1])
end

for i in 1:4
  @constraint(m, b[i,1:t] .<= k[i])
end

for i in 1:4, tt in 1:t #tt not 0
  @constraint(m, b[i,1:tt] .<= b[i,tt-1] - th[i-1,tt] + v[i,tt])
end


for i in 1:4, tt in 1:t #tt not 0
  @constraint(m, b[i,1:tt] .<= b[i,tt-1] - th[i-1,tt] + b[i-1,tt-1])
end
for tt in 0:t
  @constraint(m, th[5,tt] .== v[5, tt])
end

for i in 1:4, tt in 2:(t-1) #tt not 1 or t
  @constraint(m, th[i,1:tt] .== b[i,tt-1] - b[i,tt-1] + th[i+1,tt])
end

@constraint(m,sum(k[1:4]) <= 430)

@objective(m, Max, sum(b[5,0:t]))

JuMP.optimize!(m)

@show termination_status(m)
@show primal_status(m)
@show dual_status(m)
@show objective_value(m) ## will fail from here on if there was no solution found
@show value.(k)
@show value.(b[2,1:11])
display("text/plain", value.(th))

This should give you an idea how to use JuMP. For more see the documentation. The model as specified is unbounded or infeasible but using this example you should be able to encode the correct problem.

$\endgroup$
3
  • $\begingroup$ Hi thanks for the reply. I have been able to procure a Gurobi license and it is installed. I will take a look into what you recommended. I am also going to have to do this for multiple scenario's, is that going to be a problem using a .lp format? $\endgroup$
    – GT1992
    May 12, 2022 at 13:22
  • $\begingroup$ You will need to create an .lp file per problem you want the solver to solve. $\endgroup$ May 12, 2022 at 13:24
  • $\begingroup$ In addition to Python and Julia, Gurobi has APIs for C, C++, Java, .NET, MATLAB and R. gurobi.com/documentation/9.5/remoteservices/client_api.html $\endgroup$
    – prubin
    May 12, 2022 at 15:31
1
$\begingroup$

Using a dynamic approach like simulation optimization is still one of the best ways to tackle such a problem instead of applying an LP/MIP. Based on what you mentioned, the problem you have faced might belong to a flow shop with finite buffer capacity. (E.g. this one and lots of related papers that could be easily found by googling.). Now, by simulation approach, you can dynamically survey the behavior of the queuing system and would already see the related results of changing the problem's parameters.

As an example, suppose there is a two-stage machine queuing system with the buffer stages between the machines. The following picture is showing this system:

enter image description here

In this system, one can easily change the input parameters, run the simulation, and optimize the next output based on the previous run results. In the above system, the output of the Buffer in stage_1 is:

enter image description here

As a result, there are four jobs in the buffer, and the average time would be $0.88$ min.

$\endgroup$
2
  • $\begingroup$ Hi there, thanks for this thorough answer! It’s funny you should mention it; I aim to use simulation and LP to optimize the buffers. First I run the simulation using infinite buffer capacity to get the stochastic nature of the machines and then use those variables as input for the LP. So for each t I have the production speed of each machine and based on that I will get the ideal buffer sizes $\endgroup$
    – GT1992
    May 15, 2022 at 12:08
  • $\begingroup$ @GT1992, your welcome. it's one of the well-known methods to solve complex systems. $\endgroup$
    – A.Omidi
    May 15, 2022 at 13:17

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.