1. Introduction

Inventory management is a key problem in several industries, (car renting, storehouse space renting, etc.). It consists of managing a given fleet of equipment in order to satisfy requests to use it. When requests exceed the stock of available equipment, a decision has to be made, either to subcontract some requests to another provider or to purchase new pieces of equipment. The main difficulty lies in the fact that a subcontracted request must be subcontracted for all the duration of the request. For example, if a subcontracted car is rented to a given customer, this customer will keep the subcontracted car for all the duration of the rental. In the following, we propose a set of benchmark problem instances, derived from real-world inventory management problems.

Let us consider a warehouse that manages a stock of different types of equipment. The warehouse receives requests from customers asking for some resources of some type for a given period. Basically a request is characterized by its place in time (start and end time), by the required resource type, and by the number of resources. We suppose that all requests are known for a given period (for example, a few months or a year).

The satisfaction of all requests is mandatory. If there are not enough resources available in stock, the manager has to decide either to buy new resources or to subcontract some requests to another provider. Given the cost of all operations (rent, purchase, allocation from available stock), decisions have to made in such a way that the sum of costs is minimized.

For some resource types, items can be replaced with items of other resource types (this relation is transitive). For example, a customer requiring a small car may be allocated a medium or a large car. Obviously these replacements have a cost while customers have the same bill with or without replacement. However, in general, subcontracting a resource (or another resource) can be more expensive than replacing it with a more expensive one that is available in stock.

In general, after a given time of actual use, each resource has to be maintained. We can do the maintenance before, but after this time of use, the maintenance is mandatory. The duration of the maintenance and the number of maintenance units (for example, workers) required for the maintenance of a given resource type are known. Thus, in order to allocate resources from existing stock, some constraints have to be satisfied. On the one hand, no resource can be used more than its maximal using time without maintenance; on the other hand, equipment maintenance is planned so that the capacity of the maintenance workshop is never exceeded. Let us note that, for some resource types, maintenance is not an issue.

The main problem consists in determining

• which requests have to be subcontracted,
• which resources are allocated to those requests that are not subcontracted,
• when to buy new items, and
• at what time the resources are maintained,

so that all of the constraints are satisfied and the entire cost of the operations is minimal.

The main source of complexity of this problem lies in the fact that, for each request, the same pieces of equipment (whether subcontracted or taken from the stock) will be used throughout the duration of the request. For example, if customer X requests a resource from May 7 to May 17, customer Y requests a resource from May 13 to May 26, and only one resource is available in stock, one must decide either to subcontract a resource for X from May 7 to May 17, or to subcontract a resource for Y from May 13 to May 26. It is not possible to merely subcontract a resource for Y from May 13 to May 17, and replace the subcontracted resource by the resource originating from the stock when it returns from X, because the cost of such a replacement would be too high. (For example, a rental car company cannot replace the car used by one of its customers (Y) in the course of the rental (on May 17). This would be too inconvenient for the customer.) As a result, the problem does not merely consist of identifying the time periods over which the demand (sum of the requests) exceeds the supply available in stock. One must also select which requests to subcontract, so as to minimize the total cost associated with the requests under consideration. In the X versus Y example above, it would be wiser to subcontract X’s request, since the subcontract would run only for 10 days (instead of 13 if Y’s request was subcontracted). However, should another customer Z place a request for a resource from May 20 to May 29, it would become wiser to subcontract Y’s request, rather than both X’s request and Z’s request. This shows that the best global decision does not derive from the best local decisions: when only X and Y are considered, the best solution consists of subcontracting X’s request; when only Y and Z are considered, the best solution consists of subcontracting Z’s request; yet, when X, Y, and Z are considered, the best solution consists of subcontracting Y’s request, rather than X’s and Z’s.

The problem is further complicated by the other types of decisions that could or should be made: purchasing new resources, providing a bigger or more sophisticated resource (e.g., a bigger car) in response to a given request, and scheduling the maintenance of each individual resource. When maintenance constraints apply, they appear to be highly critical as (1) a piece of equipment cannot be allocated to a request if it needs to be maintained, (2) the maintenance facility has limited capacity, which means that a piece of equipment may have to wait (queue) before being maintained. These two factors impair the quantity of equipment that can actually be allocated from the stock. Hence, different maintenance schedules may lead to more or less subcontracting. In practice, this means that equipment allocation and maintenance scheduling decisions must be tightly coordinated, which in turn makes it necessary to decide exactly which individual pieces of equipment are allocated to each request. The following formal problem description distinguishes each individual piece of equipment. However, units of the same resource type can be considered equivalent when maintenance is not an issue.

As we mentioned in the previous section, a time period is considered for each problem. At the beginning of this period, the equipment in stock may have been used without maintenance and some requests are being handled. For the sake of simplicity we will not consider this initial state which has no effect on the complexity of the problem.

In the following, we give a formal description of the inventory management problem.

Let R = {r₁, r₂, ..., r_k} be a set of resource types. We say that the resource type r_i subsumes the resource type r_j (r_i p r_j) if any unit of type r_j can be substituted by any unit of type r_i. The Inventory Management Problem is defined by the following data:

• [Start, End] - discrete time interval such that Start, End Î N and Start £ End
• (R, p ) - set of resource types and the subsumption relation defined on it

• MCAP - capacity of the maintenance workshop
• O - set of orders

A solution is a valuation for the functions

• rent(r,o): R ´ O ® N - number of items of type r from external

• buy(r,t): R ´ [Start,End] ® P (r) - set of items of type r bought at time t

• maint(r,u): R ´ Stock(r,End) ® P (N ) - set of starting time of maintenance for the

• alloc(r,o): R ´ O ® P (r) - set of items of type r allocated to the order

such that the following constraints are verified:

1. allocated and rent resources correspond to the required resource type of the order:



and



2. all orders are satisfied:



3. at most Maxbuy(
r) items of type r are purchased during the period:



4. the same item is not allocated to two orders which intersect in time. For all o and o’ different intersecting orders in O (that is o ¹ o’ and st(o) £ st(o’) < et(o)):



5. for all items u of type r there is a maintenance after at most Utime(r) effective use. Let ord denote the ordered inverse of the function alloc: ord(u) is an ordered set of orders o such that u belongs to alloc(r,o) for some r in R. ord(u) is ordered by the starting time (st) of its elements. Let S(u) denote the set of consecutive subsets (intervals) of ord(u), and for all s in S(u), l(s) denote the sum of the duration of the orders in S(u), st(s) the starting time of the first order in s and et(s) the end time of the last order in s.



However, if an order o requests a resource of type r and if the duration of o is greater than Utime(r), a resource u of type r can be assigned to o provided that o is the only order scheduled between two consecutive maintenances of u including o. In other terms, the above constraint does not apply when s = {o}.

6. at each moment, the sum of the maintenance capacities required by the items in maintenance should not exceed the capacity of the maintenance workshop.

The overall problem is NP-hard in the strong sense. Indeed, given an instance of the multiprocessor scheduling problem [1] i.e., a set of tasks T, a capacity MCAP, a duration d(t) for each task, and an overall deadline D, one can easily create an instance of the inventory management problem which accepts a solution with no external rental if and only if the multiprocessor scheduling problem accepts a solution (for each task t in T, create a resource type r_t with Mtime(r_t) = d(t), Utime(r_t) = 1, Mcap(r_t) = 1, and two orders for this resource type, the first finishing at time 0, and the second starting at time D).

A series of instances of the above problem is available on the web site http://www-icparc.doc.ic.ac.uk/chic2/benchmarks/inventory.htm. This section describes the input and output data format for these benchmarks.

The input file is composed of four parts in the following order:

• definition of the global variables of the problem (period and capacity of the maintenance workshop)

globals(start,end,mcap)

• definition of resource types as a sequence of individual resource type definition. A resource type is defined in the following way:

resource(rtype_id, Stock, Utime, Mtime, Mcap, Crent, Cafix, Catd,

Cbuy, Cstock, Cmaint, Maxbuy)

resource(1, 2, 150, 10, 2, 15, 13, 5, 1, 1, 4, 0)

• definition of the substituability relation by a sequence of blocks

substituable(rtype_id1, rtype_id2)

substituable(2, 1)

• definition of the set of orders by a sequence of individual order definition:

order(order_id, st, et, rq, rtype_id)

order(2, 0, 35, 2, 1)

If there is maintenance, we consider that a unique integer identifier is attributed to each unit of each resource type. Since at the beginning the units are equivalents, the identifiers have to be defined by the programmer and they appear only in the output file. If maintenance is not considered, the output file is defined by three blocks:

• rentals (predicate rent), a sequence of lines of format

• purchase (predicate buy), a sequence of lines of format

• allocations (predicate alloc), a sequence of lines of format:

If maintenance is considered, the output file is defined by four blocks:

• rentals (predicate rent) - as in the previous case
• purchase (predicate buy), a sequence of lines of format

• allocations (predicate alloc), a sequence of lines of format:

• maintenance (predicate maint), a sequence of lines of format:

In this example, 4 resources of type 1 are available in stock. Maintenance is not considered. In the time interval [0,100] we have to satisfy three orders. These orders are defined by their starting time (st), end time (et), required resource type (rtype), and required quantity (rq):

rent(1,1,2)

rent(1,3,1)

alloc(1,2,3)