Re: linear programming problem
- From: Ray Vickson <RGVickson@xxxxxxx>
- Date: Mon, 28 Jul 2008 12:51:27 -0700 (PDT)
On Jul 28, 11:13 am, Luting <houlut...@xxxxxxxxx> wrote:
On Jul 28, 10:24 am, Ray Vickson <RGVick...@xxxxxxx> wrote:
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 fromhttp://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- Hide quoted text -
- Show quoted text -
Hi Prof. Vickson,
Thank you so much for explaining this in such a detail.
You remind me the inventory parameter! Yes, we allow inventory. We
don't need to produce the EXACT number each day according to the order
amount. But we do hope our inventory at the end of everyday >= the
order amount.
My main problem is how to deal with the back-orders. I think the
introducing of positive/negative inventory will solve the problem.
Now I have another doubt. What should be the goal? MIN sum(Inij)?
The appropriate goal is not a "mathematical" question at all, but
typically more like an economic one or a managerial one. Are you
talking about a privately-owned, profit-making firm? If so, then
profit maximization or cost minimization (sometimes, but not always
the same) seems appropriate. For the sake of argument, say you decide
to try for total (variable) cost minimization. Then you need to know:
the unit production costs of products at plants and by days of the
week. (Usually in such problems we assume the same costs on Monday,
Tuesday, etc., but sometimes this is not the case; for example, if
workers on Sunday earn more than workers on weekdays, the wage costs
per unit are different. And if ingredients are "fresher" and more
effective on Monday than on Friday, then the costs could be different.
However, you need to be the judge of that.) You also need to know the
unit cost of holding inventory---see Nahmias' book for a discussion of
what are the components of holding cost. Usually the main holding cost
component is taken to be the cost of capital, or carrying cost
associated with storing, rather than selling an item. However, other
costs may enter as well, such as costs of heating, lighting, warehouse
rental, etc. These matters can be VERY tricky, however. For example,
there may be diesel-fuel costs for the fork-lift trucks needed to move
the items into storage and out again. Whether such costs are part of
the holding cost or just part of fixed overhead depends on the extent
to which they vary with the amount of storage; we shouldn't
necessarily just take last year's cost of moving 1 million items and
divide by 1 million to get a unit cost: maybe only part, of the cost,
or none at all should be included. There are similar, sometimes even
harder and subtler issues associated with the backordering penalty per
unit. Often decision-makers are so uncertain and uneasy about giving
accurate figures that they prefer to use "reasonable" estimates and
then do sensitivity analysis.
Anyway, if you know the unit production costs cij of item j at plant
i, the unit holding cost hj for item j (assumed to be the same at
different plants and on different days) and the unit backordering
penalty pj for item j, an appropriate total cost for minimizing would
be
C = sum{i=1..7,j=1..3} [c1j*xij + c2j*yij] + sum{i=1..7,j=1..3}
[ hj*Ipij + pj*Inij]. Here, i = day and j = product. The constraints
would be the inventory-defining constraints, production capacities,
possibly others you have not mentioned, and policy-limitation
constraints, if any (such as no inventory carried from one week to
another, or no backordering from one week to the next). There seems to
be no logical reason to have such additional restrictions, but they
may apply anyway by corporate fiat. Again, only you know the full
story.
R.G. Vickson
.
- References:
- linear programming problem
- From: Luting
- Re: linear programming problem
- From: Ray Vickson
- Re: linear programming problem
- From: Luting
- linear programming problem
- Prev by Date: Re: Point Torus
- Next by Date: Re: Roundess as a shape coefficent
- Previous by thread: Re: linear programming problem
- Next by thread: Congruence modulo p^2
- Index(es):
Relevant Pages
|
