Rental Scheduling Problem

The Rental Scheduling Problem minimizes the cost of the plans purchased while satisfying the number of units needed for each period (the covering constraints). The structure of this problem is very similar to the employee problem, except for the addition of these plans, or options. These plans can have different effective number of periods, and different costs as a result. Note that the “plan length” would be pseudo-equivalent to the ShiftLength in the employee problem. Additionally, these plans may be restricted to only having certain start periods - for example, there may be a weekend plan that can only start on Saturday (and is effective Saturday and Sunday). This requires connecting the plans to the periods which they can start in, which is done through the PlanToPeriod parameter. This type of problem can arise when renting cars or other types of equipment.

Definitions

Sets

  • Periods - An ordered set of periods when the units are needed

    • p in Periods or \(p \in P\)

  • Plans - Set of plans that are available to rent units

    • a in Plans or \(a \in A\)

  • PlanToPeriod - A set that describes which periods a plan can start in. This set is 2 dimensions, consisting of tuples \((p,a)\). Note that not all combinations of \((p,a)\) for \(p \in P\), \(a \in A\) may exist in this set.

    • (period, plan) in PlanToPeriod or \((p,a) \in J\) or \(j \in J\)

Parameters

  • PeriodReqs - measure of number of units needed for Period p

    • PeriodReqs[p] for p in Periods or \(R_p \enspace \forall p \in P\)

  • PlanCosts - measure of the cost of reunting one unit under Plan a

    • PeriodReqs[a] for p in Periods or \(C_a \enspace \forall a \in A\)

  • PlanLengths - measure of how many periods in a row a Plan a is effective for

    • PlanLengths[a] for a in Plans or \(L_a \enspace \forall a \in A\)

Decision Variables

  • NumRent - number of units that are rented starting on Period p and under Plan a

    • NumWorkers[(p,a)] for p in Periods for a in Plans or \(X_{(p,a)} \enspace \forall (p,a) \in J\) or \(X_{j} \enspace \forall j \in J\)

Objective

Minimize cost of the purchased plans. Note that we have to make sure that the combination of Period p and Plan a exists in PlanToPeriod, or \((p,a) \in J\).

\[\text{Min} \sum_{a \in A} C_a \sum_{p \in P \, \mid \, (p,a) \in J} X_{(p,a)}\]

Constraints

  • The covering constraints require that there are enough units available in each Period p. To obtain the number of units available in each period, we need to use the decision variables NumRent[(p,a)] in combination with the plan lengths PlanLengths[p]. The number of units available in each period would be the sum of all of the NumRent[(p,a)] that are effective during the covering contraint’s Period p. In other words, we have to look through all of the plans, and see which periods they can start in, and determine whether or not that combination symbol will be effective in the constraint’s Period p based on the PlanLengths[p]. This effective condition will be represented by the math symbol \(f\). In mathematical terms, these constraints can be represented by

\[\sum_{j \in J \, \mid \, f} X_j \geq R_p \quad \forall p \in P\]

where \(P\) is a cyclically ordered set (or a cycle).

  • The decision variables must be greater than or equal to zero and integer.

\[X_j \geq 0\text{, int} \enspace \forall j \in J\]

API Reference

See the corresponding section in the API Library Reference to learn more about how to use the API for this problem class.