TopCoder problem "MRP" used in SRM 34 (Division I Level Three , Division II Level Three)



Problem Statement

    
PROBLEM STATEMENT:

Class name: MRP
Method name: calcOrderSize
Parameters: int[], int, int, int, int, int
Returns: int

The Material Resource Planning (MRP) Explosion gives us the quantity of low
level components needed to build our product.  Generally, most of the
components must be purchased from suppliers - which brings up a number of
issues (and terms):

There is a fixed cost associated with placing an order (contracting with a
supplier, placing a purchase order [PO], delivery charges, etc) known
collectively as the "order cost".  "Lead time" is the time taken between
placing an order and receiving the goods.  

One of the goals of MRP is to calculate the optimal order size ("Economic Order
Quantity") that will minimize costs over a period of time (usually a year).
The order size represents the number of units purchased with each order and is
set at a fixed amount over a certain time period (usually a year) by contracts
with suppliers.  If you are manufacturing pencils and need to order the eraser
heads, it's generally less costly to place an order for 500 eraser heads than
it is to place 500 orders of one eraser head.  Between those two choices, an
order size of 500 is probably more optimal.

Implement a class MRP, which contains a method calcOrderSize.  The method
calculates and returns the optimal order size that:
1) Prevents a stock out situation (not having enough inventory to meet the
forecast for the month)
2) Will minimize total costs over a 12 month forecast.

The method signature is:
int calcOrderSize(int[] forecast, int initialInventory, int costPerUnit, int
costPerOrder, int leadTime, int holdingCostPerUnit)
Be sure your method is public.

TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
*The forecast int[] will contain 12 entries representing 12 months.  Month 1
will be index 0, month 2 will be index 1, etc.
*Each forecast element will be between 1 and 1000 (inclusive)
*The initialInventory will be between 0 and 1000 (inclusive)
*The costPerUnit will be between 1 and 50 (inclusive)
*The costPerOrder will be between 1 and 50 (inclusive)
*The leadTime will be between 0 and 12 (inclusive)
*The holdingCostPerUnit will be between 1 and 50 (inclusive)
*The initialInventory will be great enough to prevent a stock out during the
initial lead time.  In other words, if lead time is 2 months - the initial
inventory will be greater than or equal to the sum forecast for the first 2
months (thus preventing a stock out in either of those months).

Notes:
*A lead time of 0 means the inventory is delivered immediately within the same
month.  A lead time of 1 means the inventory is delivered in the month
following the order.
*Do not worry about inventory levels after month 12.  In other words, if your
lead time is 3 months - you should not be placing any orders in months 10, 11
or 12 because the inventory is delivered past month 12.
*If more than 1 order size is optimal (both give the same minimal cost), return
the lower order size.
*When calculating the cost for a specific order size, you can place more than 1
order per month.  If you are calculating the cost for an order size of 5 and
are in need of 45 items in month 1 and 30 items in month 2, you can place 9
orders in month 1 and 6 orders in month 2 to meet the need (given a lead time
of 0). See the example below.

Cost for any given month can be calculated as:
	costPerOrder * # of orders made that month
+ costPerUnit * # of units delivered for the month (lead time may make the
months different)
+ holdingCostPerUnit * inventory from prior month (only if the prior month had
inventory to carry over)
	(prior month inventory for the first month is initialInventory)

If you are evaluating an order size of 2 with an input of
({10,10,10,10,10,10,10,10,10,10,10,10},3,1,3,0,1)...

     Month:    1   2   3   4   5   6   7   8   9  10  11  12
-----------  --- --- --- --- --- --- --- --- --- --- --- ---
Start Inv.:    3   1   1   1   1   1   1   1   1   1   1   1
- Forecast:   10  10  10  10  10  10  10  10  10  10  10  10 
=Inventory:   -7  -9  -9  -9  -9  -9  -9  -9  -9  -9  -9  -9

    Orders:    4   5   5   5   5   5   5   5   5   5   5   5

 Inventory:   -7  -9  -9  -9  -9  -9  -9  -9  -9  -9  -9  -9
+  Ordered:    8  10  10  10  10  10  10  10  10  10  10  10
= End Inv.:    1   1   1   1   1   1   1   1   1   1   1   1

 Hold Cost:    3   1   1   1   1   1   1   1   1   1   1   1
+Ord. Cost:   12  15  15  15  15  15  15  15  15  15  15  15
+Unit Cost:    8  10  10  10  10  10  10  10  10  10  10  10
=Tot. Cost:   23  26  26  26  26  26  26  26  26  26  26  26

Overall cost of order size 2: 309, which for this example is NOT the minimum
cost. Different order sizes would have to be evaluated in order to calculate
the minimum cost. The minimum cost for this example is 192 which is for an
order size of 10.

In month 1, we start with an inventory of 3.  Taking away the forecast of 10
creates a stock out of 7.  To cover the stock out, we place 4 orders of 2 (the
order size).  The 8 units ordered are delivered immediately (lead time is 0)
giving an ending inventory of 1.  The cost for month 1 operations is 3 (initial
inventory of 3 * holding cost of 1) + 12 (4 orders * order cost of 3) + 8 (8
units delivered this month * cost per unit of 1) = 23.
In month 2, we start with an inventory of 1 (ending inventory from month 1).
Taking away the forecast of 10 creates a stock out of 9.  To cover the stock
out, we place 5 orders of 2.  The 10 units ordered are delivered immediately
giving an ending inventory of 1.  The cost for month 2 operations is 1
(starting inventory of 1 * 1) + 15 (5 orders * 3) + 10 (10 units delivered this
month * 1) = 26.
Continue until all 12 months have been processed.  The cost for order size 2 is
309 (which is the sum of each month's cost).

For an order size of 10, the cost would be 192, which would be the minimal cost.


Examples:
An input of ({10,10,10,10,10,10,10,10,10,10,10,10},3,1,3,0,1) returns 10
(minimal cost of 192)
An input of ({10,10,10,10,10,10,10,10,10,10,10,10},5,1,2,0,1) returns 5 (cost:
166)
An input of ({1,1,1,1,1,1,1,1,1,1,1,1},0,1,1,0,1) returns 1 (cost: 24)
An input of ({1,1,1,1,1,1,1,1,1,1,1,1},0,1,5,0,1) returns 3 (cost: 44)
An input of ({1,1,1,1,1,1,1,1,1,1,1,1},0,1,5,0,3) returns 2 (cost: 60)
An input of ({1,1,1,1,1,1,1,1,1,1,1,1},12,1,5,0,3) returns 0 (cost: 234)
An input of ({23,45,23,56,123,36,21,67,12,34,56,22},68,2,5,2,1) returns 30
(cost: 1193)
 

Definition

    
Class:MRP
Method:calcOrderSize
Parameters:int[], int, int, int, int, int
Returns:int
Method signature:int calcOrderSize(int[] param0, int param1, int param2, int param3, int param4, int param5)
(be sure your method is public)
    

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=185

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4005&pm=185

Writer:

Pops

Testers:

Problem categories: