Background
In operations research, a key problem involves balancing limited and uncertain resources for the maximization of a specific business objective under constraints (such as budget or time). Approaches for this problem are frequently domain-specific due to the variability in design variables.
For simpler problems such as hub-and-spoke placement design, one can use proximity (i.e. distance) as a target, leading to clustering-based approaches ((Ruan et al. 2016)) which focuses on minimizing resource distance to solve a specific task. In others probes, however, clustering based approaches do not show a clear advantage due to the fact that they involve resource allocation decisions on a non-linear space (unlike physical space) subject also to non-linear constraints (unlike time).
(Luo et al. 2021) provides a succinct summary of various approaches used for cloud computing optimization; a vast majority of problems in that domain can be qualified as “resource allocation” problems, whereby one seeks to maximize the ordering of specific renewable resources’ utilization to maximize uptime. This type of problem is also seen in hospital resource allocation ((Visintin et al. 2017))—whereby the finite (due to limited bedcount) and renewable (due to patients leaving/dying) resources are optimized for maximal throughput.
Approaches exist to mix scheduling-based optimization and resource based optimizations for specific domains such as disaster relief ((Baxter, Wilborn Lagerman, and Keskinocak 2020)). Yet, these approaches are generally much more widely adaptable than the specific domains on which they are applied.
As such, this proposal seeks to provide a formalization of combined scheduling and resource allocation problems, which the proposed project will seek to solve using a variety of approach and explore an application of this generic formulation through the task of executive time scheduling.
Formulation
We formalize the task of resource management as an optimization under uncertainty scheme. Critical to this formalization is the choice that the objective function of this formalization under any parameters is minimizing time—that is, unlike classic resource allocation tasks, we do not consider the maximization of throughput or utilization as an objective.
We make this decision informed by the fact that any resource allocation problem is either unsolvable completely (due to the resource being fundamentally constrained to perform a unit task), or solvable trivially without considering time (by simply allocating in a queue), while any scheduling problem naively already uses minimizing time spent as the optimization objective. Therefore, by minimizing for time, our solver should then optimize for secondary objectives such as utilization.
Further, we consider time to be absolute with respect to \(t^{(0)}\), the epoch. As such, we obtain an optimization problem that:
\begin{align} \arg\min_{\theta}\ & t^{(f)}_{\theta} - t^{(0)} \end{align}
To obtain \(t^{(f)}\), we create a temporal dependency relation through all objects (i.e. the design variables) within the system—in effect creating a Gantt chart upon which we perform our optimization (in effect, automating approaches such as (Doolen and Van Aken 2016)); the final timestamp of the dependency relation can then serve as our value for \(t^{(f)}\).
To support this formulation, therefore, we have to formalize every other secondary objective in terms of an object with a temporal dependency. To do this, we provide fundamental primitives here upon which a computations graph for \(t^{(f)}\) can be generated; the product of all parameters of the primitives used forms the design variable upon which optimization occurs.
Block
a “block” is a fixed region of time \((t_{1}, t_2)\) where \(t^{(0)} < t_{1} < t_2\) for which no other primitives can be scheduled. Its existance does not change \(t^{(f)}\).
Event
A event is a unit of work with fixed time window, each with a specific dispatch time and duration. If our schedule contains \(n\) events, we demand that \(t_{\theta}^{(f)} > t_{n}^{(1)}\) where \(t^{(1)}_{n}\) is the ending time of the last event.
If an event is scheduled atop a Block, its end time is increased by the duration of that block.
An event always exposes at least one design variable, dispatch time, which is when the event shall take place; further, it may expose any set of categorical parameters to choose from. Importantly, the duration of each event is neither a parameter nor a design variable in this system; it is a computed, random variable value (making this an optimization under uncertainty problem) of the design variables and schedule (due to resource allocation constraints). The Operationalization section below provides more details on this fact.
Task
A task is multiple events and tasks in dependent order, meaning each event must conclude when the other begins.
Schedule
A schedule is a combination of tasks and blocks which are internally dependent. In effect, our optimization problem becomes the act of choosing dispatch times of events which is allowable by the schedule.
\begin{align} \arg\min_{\theta}\ & t^{(f)}_{\theta} - t^{(0)} \\ s.t.\ &\theta \in \text{schedule} \end{align}
Operationalization
We give here a sketch of two common resources which are allocated through optimization techniques, and how the framework outlined above allows them to be formalized.
Constrained Resource Allocation
Consider the case where there are \(n\) possibly-divisible units of work to be completed by \(w\) workers. In the fashion outlined in ((Cavalcante, Cardonha, and Herrmann 2013)), each work unit \(n\) is considered a Task, subdivided into one to multiple Events based on the nature of the task.
To compute \(t_{2}\) of each event, we greedily ((Lee et al. 2013)) assign the event to the first available worker at that point, and, if a worker is not available, we add to \(t_2\) the wall time until the an worker becomes available. As such, the task of choosing the correct sequence of wall times becomes a proxy for allocating worker usage; for instance, if a task with a dependency needs to start earlier, moving other tasks’ dispatch times to when the dependent task started is a proxy for assigning the dependent task first to a worker.
Traffic Allocation
If a transportation task is needed, we formalize it as a single Event. This event has uncertain duration (due to traffic). The high-level choices of routing are exposed as a parameter to this event, while the details are computed directly and taken as oracle data.
Optimization
Tasks and their dependencies are an abstraction over the choices of a sequence of events. With a certain Event order chosen, one can solve the optimization problem with a two step, iterative approach.
- choose parameters: we formulate event “parameters” as categorical here, so its possible to perform simple grid search to choose parameters; if the parameter space is large, approximate bracketing approaches maybe sufficient to choose each parameter
- optimization: using the method of dual numbers, we use the selected parameters to create a computation graph for \(t^{(f)}\) with uncertainty; this is our design objective for which we can use local model methods or direct methods to solve
Once an optimal choice of \(2\) is obtained, we return to step \(1\), fixing our choices of dispatch times, for an reevaluation of parameters. We repeat until this scheme converges.
Implementation
For each Event, we provide an interface to compute its duration based on dispatch time and state (the other chosen dispatch times.) Event durations are computed left-to-right in order for all previous events of a computation to already have both an associated dispatch time and ending time.