Several operations research problems include planning over a discrete horizon. In such situations, actions taken at a given moment from the timeline will affect how decisions should be performed in the future. For instance, production and inventory planning usually includes balancing between holding inventory costs, setup costs, stock coverage, and demand forecast, among other aspects. The amount produced of a given product at a given moment is usually a decision to be taken and it should affect the product availability not only when produced but also in the future when considering the possibility of stocking goods.
Inventory balance
To calculate inventory balance, let us define a discrete planning horizon T with instants t. The inventory at a given moment will be a decision variable I indexed by the elements of the set T. If we define inputs (for instance the number of items produced) and outputs (corresponding demand or items transported) of a given moment as x and d respectively, we can compute the final inventory at a given moment as the final inventory of the previous moment plus inputs minus outputs.
Remember the inputs and outputs might be fixed parameters of the problem or also decision variables.
We can put it in equation form as the following.
A great example to illustrate this is the Dynamic Lot-Size model. However, more complex decisions might be involved in the process and new elements should be included in the inventory balance equations then. One example will be presented right next.
Inventory with backlogs
Now suppose we have deterministic demands d for each moment t, but we might decide to postpone some of them to reduce our costs (for instance setup costs or fixed charges in transportation systems). These might become backlogs in an inventory balance equation, usually with some associated cost in the objective function(s). Once again consider our inputs are represented by x, but now we are also going to include a non-negative decision variable for backlogs b, also indexed by t. The new inventory balance equation becomes the following.
Then it is up to the optimization solver to define when a demand should be postponed to reduce overall costs.
Starts and Endings
Some planning processes include scheduling activities that start at a certain moment and might last for more than one instant in the discrete planning horizon. When inserting these decisions in an optimization model, usually it is up to the model to define when the activity starts, when it ends, and possibly its corresponding duration. Therefore, we must include some binary decision variables to represent these decisions.
To a better understanding of the modeling expressions, let us visually represent an activity that starts at a given moment, is active during some instants of the planning horizon, and then ends.
Notice that an activity starts in a moment in which it is active but it must be inactive in the previous instant. Conversely, at its ending, there’s no rule regarding the previous instant but it must be inactive in the following one.
To write that into mathematical expressions, let us use three groups of decision variables — all of them indexed by the elements of the planning horizon T. The variable x will be used to denote a moment in which the activity is active, y will denote its start, and z denote its ending.
To obtain a tight linear relaxation and help the solver during Branch & Bound, three groups of constraints will be created to establish the relationship between x and y, and the same between x and z.
To identify starts:
And to identify endings:
Additional implication constraints might be included in the first and last instants to ensure the desired relationships between x, y, and z in these moments.