Re: linear programming problem

On Jul 28, 8:40 am, Luting <houlut...@xxxxxxxxx> wrote:
Hi, I am trying to solve a scheduling problem.
We get orders every Sunday, and then schedule the production for the
following week. The order is as follows:

Prod1 Prod2 Prod3
M 4 1
T 1
W
TR 2 1
F 1
SA
S 2

The numbers indicate the amount of products we need produced BY this
day.
And we have schedule tables for two plants like this:

Plant 1:
Prod1 Prod2 Prod3
M x11 x12
T x21 x22
W x31
TR .... ... ...
F
SA
S x71 x73
---------------------------------------------
Plant 2:
Prod1 Prod2 Prod3
M y11 y12
T y21 y22
W y31
TR .... ... ...
F
SA
S y71 y73
---------------------------------------------

It's not a simple linear programming since we need to consider the
difference of the deadline of each order. e.g.
SUM(x11:x71)+SUM(y11+y71)=4+1+2.

Are you saying that in the whole week you must produce /exactly/ as
much of product 1 as is demanded that week, with no product carryover
to next week and no demand carryover to next week?

This is one of the constraint, but
not all. x11and y11 should cover the order on first day, therefore
x11+y11>=4. Plus, each plant has limits of the amount it can produce
per day. So it's very possible that the order cannot be met. In this
case, we need to add the delayed order to the following day and try to
meet it there.

I am really confused how to write the constraints to represent this
problem.
Can anyone give me some hint?
Is there any special algorism I can use?

Many thanks.

Most problems of this type also have inventory variables, so if you
produce more than 4 units on day 1, the excess can be carried over to
subsequent days to help meet demands then. Of course, this assumes non-
perishable output (although there are also deteriorating-item
inventory models available); and, of course, you also need somewhere
to store the inventory, and that will also have a cost (usually
assumed to be proportional to the level stored). Note that inventory
carryover is essential in problems with limited production capacity
and highly variable demand patterns. Also, inventory on left over on
Friday night can help meet demands next week, again if th item is not
perishable (or not too quickly perishable) and you have storage space,
or if it is allowed by managerial policy. You can even have negative
inventory, which corresponds to back-ordering; this is what you refer
to as adding the delayed order to the next day. Of course, there may
also be back-ordering costs. Altogether, the cost of inventory, I, may
have the form c(I) = h*I if I >= 0, and = -p*I (= p*|I|) if I < 0,
where h = holding cost per unit of physical inventory and p = penalty
cost per unit backordered. This CAN be represented linearly: let I =
Ip - In, where Ip, In >= 0, and let c(I) = h*Ip + p*In. Note that in a
cost-minimization model with both h > 0 and p > 0, the optimal
solution will have the property that either Ip = 0 or In = 0 (so that
an inventory I = 5 will always have the form I = 5 - 0, rather than I
= 6 - 1 or I = 7 - 2, ...). Of course, the parameters h and p can vary
between the products and possibly even between production plants. Note
that if there is no storage space, so no physical inventory is
allowed, you can still have the "negative inventory = backordering"
variables.

Here is how I would model the problem; Let Iij = Ipij - Inij be the
inventory of product j at the end of day i. Let Ii0 = Ipi0 - Ini0 =
initial inventory or backorders from last week. The Ii0 are not
variables, but are input data. If Ipi0 > 0 we can reduce the demand
for product i on day 1 by Ip0 units; if Ini0 > 0 we can just add Ini0
to the demand for product i on day 1. So, we have Ip10 - In10 + x11 +
y11 = 4 + Ip11 - In11,
Ip11 - In11 + x21 + y21 = 1 + Ip21 - In21,
Ip21 - In21 + x31 + y31 + x41 + y41 = 2 + Ip41 - In41,
etc., with similar constraints for products 2 and 3 Of course, there
are also production capacity constraints that couple the three
products together at each plant. If you are not allowed to carry over
inventory past Sunday night you can set Ip7i = 0 and if you are not
allowed to delay demand over the weekend you can set In7i = 0. If you
are not allowed to carry inventory at all, just set Ipij = 0 or leave
these variables out of the formulation altogether. The formulation
above assumes that inventory from both plants can be stored in a
common warehouse; if not, you need a separate inventory variable for
each plant, product and day. However, backorders do not consume
physical space, so a common backordering variable Inij can apply to
all plants.

It sounds like you might benefit from reading a chapter or two of a
"production management" textbook. Many of them are quite dreadful (at
least for a mathematically-inclined person) but there are some good
ones that also have lots of material on production-inventory
modelling. One of the better ones is "Production and Operations
Analysis", by Stephen Nahmias. An Amazon customer review says "This
books is one of the most complete books in Production matters. It has
good theory on production and operations, and the applications to real
life problems is impressive. Good for students, professors and
professionals." It does not really matter if you get the most recent
(overpriced?) edition---any used copy will do. A source covering very
many of the issues touched on above is the old but still good book
"Applied Mathematical Programming" by Bradley, Hax, and Magnanti
(Addison-Wesley, 1977). I don't know if it is still in print, but it
can be downloaded for free from http://web.mit.edu/15.053/www/ .
Another book covering problem like yours is "Production and Inventory
Management", by Hax and Candea, Prentice Hall 1983.

Good luck.

R.G. Vickson
Adjunct Professor, University of Waterloo

.

Relevant Pages

  • Re: Good economic news! + metalworking
    ... producing at normal production rates and pack the rafters with product. ... imagine my smile when my customers call in a panic because their ... they don't keep expecting the zero lead time, I can't afford this inventory ... I'll bet they will want to rebuild their safety stock all at ...
    (rec.crafts.metalworking)
  • Re: Good economic news! + metalworking
    ... producing at normal production rates and pack the rafters with product. ... imagine my smile when my customers call in a panic because their ... they don't keep expecting the zero lead time, I can't afford this inventory ... I'll bet they will want to rebuild their safety stock all at ...
    (rec.crafts.metalworking)
  • Re: linear programming problem
    ... and then schedule the production for the ... Most problems of this type also have inventory variables, ... between the products and possibly even between production plants. ... so a common backordering variable Inij can apply to ...
    (sci.math)
  • Re: linear programming problem
    ... and then schedule the production for the ... inventory models available); and, of course, you also need somewhere ... Altogether, the cost of inventory, I, may ... between the products and possibly even between production plants. ...
    (sci.math)
  • Re: Help with table structure for manufacturing production counts
    ... I currently receive a weekly report from the plant managers that gives Model numbers, quantity built, and how many have each various options (ie: color, glass doors, casters, compressor hp, voltage etc). ... The buyers in the purchasing department use the data from this report to help them keep track of inventory of their purchased components and predict what they need to buy in the upcoming weeks. ... I began to set up a table to use to house the data that comes from the weekly production reports ...
    (microsoft.public.access.gettingstarted)