Permutation job scheduling with partial available machines

algorithm, evolutionary-algorithm, genetic-algorithm, search

Solution

Overview

Although you've explicitly tagged `evolutionary-algorithm`, I'd suggest you to have a look on a set of algorithms summarized under the name Approximate Dynamic Programming (ADP). In my opinion a good introductory book is the one of Warren B. Powell. It contains a lot of such ressource allocation problems, as well as several other practically relevant stuff which often goes under the name of Optimal Control (example: controlling a trucking company having several thousands of trucks).

One advantage ADP has over directly applying evolutionary-algorithms, simulated-annealing and so on is that it doesn't present a specific algorithm, but rather a framework for modeling time-dependent Markov decision problems. Within these framework, one is free to employ a variety of appropriate algorithms.

In order to apply ADP, one key is the correct mathematical modelling of the given problem. Of central importance is the `state` of the system, the `actions` one can take in a given state as well as the `cost` these actions require and which one wants to minimize -- your costs here are given by the duration of the test. Given one has constructed an appropriate model, the task is then to (approximately) solve the Bellman equation, for which several algorithms exist.

In the following, I'll give an example of how one can proceed here. This is naturally not a ready-to-use model, as such might take a rather long time to build -- actually I think this would be a fine problem for a masters or even a PhD thesis. However, I'll try to keep it exhaustive in a first step, such that one can introduce approximations later on.

Modelling the state of a single battery

First we are going to set up a rough model for a single battery. Here it is helpful that your problem is as deterministic as you described, i.e. that there are no stochastic components here (for example, that all durations are fixed and not randomly drawn from some statistical distribution).

Single state: As you wrote, one battery is given by a state

S = {SoC, Relax}      where SoC   \in {UNKNOWN, 0%, 25%, 50%, 75%, 100%}
                      and   Relax \in {UNKNOWN, 0m, 5m, 15m, 30m, 1h, 2h, 6h, 24h}

I've added `0%` and `0m` for convenience, although they are maybe not really needed here.

Note that I've already made a large simplification here, as the State-of-Charge can also be `79%`, for instance. The assumption which justifies this is the following: once you start your experiment for the first time (or also anew after a long time), all batteries are reasonably in the state `{UNKNOWN,UNKNOWN}`. Then, according to your description, the first one has to do is to do a full recharge, which sets all to the state `{100%,0m}` (and which costs `2,5h`). From here, one only does qualified state changes -- discharging is done only to specific `SoC`'s, and recharching only to `100%` (this I assumed based on your description). Note that this becomes harder in a more natural stochastic framework, where for instance the batteries' `SoC` is not that well-behaved.

Actions and costs: for specific single-battery states, one has associated a set of feasible actions (plus their corresponding costs). Let's collect them in the following:

State                  Possible Actions                       Cost
-------------------------------------------------------------------------------
{UNKNOWN, Relax}  ->   RECHARGE TO {100%,0m}                  2,5h

{SoC, 0m}         ->   RELAX TO {SoC,5m},                     5m          

{SoC, Relax}      ->   RECHARGE TO {100%,0m},                 2,5h           
                       DISCARGE TO {SoC-1},                   C(SoC, SoC-1)
                       DISCHARGE-MEASURE TO {SoC-1},          C(SoC, SoC-1)
                       RELAX TO {SoC, RELAX+1}                C(Relax, Relax+1)

{SoC, UNKNOWN}    ->   RECHARGE TO {100%,0m},                 2,5h
                       DISCARGE TO {SOC-1,0m},                C(SoC,SoC-1)   
                       RELAX {SoC, 24h}                       24h

`SoC-1` here stands for the next feasible state, whereas `C(SoC, SoC-1)` means "time to go from SoC to SoC-1, eg. from 75% to 50%. It's your turn here to check this table whether it meets your model. If not you have to correct or extend it.

Note that I've made again a simplification by allowing only transitions to the next feasible state `SoC-1` (e.g., from 75% to 50%). This is reasonable as the cost is assumed as additional. For example, when you go from 75% to 25%, it takes the same time as when going first to 50% and then to 25%.

Further, all `RECHARGE` and `DISCHARGE` actions are feasible only in the office hours, which has not been accounted for in the above table (but which needs to be incorporated later in the model).

Combine the above to a model of the complete system

Now let us assume you have `N` batteries, `M` rechargers and `K` dischargers (where we can assume `M<=N` and `K<=N`), all of which are identical. Further, let's say the goal is to perform each test only once.

Test state: The test state `Test` is a vector of dimension `4*7` of `0`'s and `1`'s containing the information whether a specific test has already been performed. Note that this corresponds to `2^28` possible states, so one definitely has to introduce an approximation here.

Multi-Battery state: The combined state of all batteries `B` is the cartesian product of the single-battery state, i.e. it is in the space `{SoC,Relax}^N`. That means simply that one needs to consider `N` single-battery states.

B={SoC_1, Relax_1}, ..., {SoC_N, Relax_N}

Again, the size of this space is is going to be a very large number for moderate numbers `N`.

Office time: Further, we need to incorporate the time of the day `T`. Doing it exactly, one ends up with a number of `24*60m / 5m = 288` possible five-minutes slots.

Multi-Battery actions: Similarly, the multi-battery actions are given by an `N`-dimensional cartesian product of the one dimensional actions. `RECHARGE` and `DISCHARGE` is only feasible for `T` in the offcie hours and if enough Re- and Dischargers are available (the sum of all `RECHARGE`/ `DISCHARGE` must not exceed `M`/`K`).

Summarizing, the complete state `S` is given by the combination

S = {Test, T, B}

The dimension of the state space is about `2^28 * (6*9)^N * 288` which quickly becomes huge.

Further, for each state there is a corresponding set of allowed actions which should be clear by now.

So now that the model of the system has been specified more or less (correct it if needed!), we can go on by trying to solve it.

The Bellman equation

The Bellman equation is the central equation of (approximate) dynamic programming. For a nice introduction have a look at the book of Sutton and Barto which is freely available on the net.

It's idea is rather simple: for each possible state, introduce a value function `V(S)` which tells you how good it is to be in state S. This value function in principle contains the time needed to finish the tests once you are in state S. In order to determine this value for a finite-horizon problem as this is, one starts from the end state and recurses until the beginning -- that is, at least if the size of the problem allows it. But let's do this schematically in the following and see:

The final state is the one where `Test` contains only ones, i.e. all `28` tests have been performed. Set `V(S)=0` for all these states (regardless of `T` and the multi-battery state), as you do not need any more time.

One step back: Now consider all states where `Test` has only 27 ones and one zero, i.e. one test still needs to be performed. For each possible multi-battery state `B` and time point `T` one can automatically spot the quickest alternative. Set `V(S)` equal to this cost.

Another step back: Next one considers all states where `Test` has only 26 ones and two zeros (two tests still to be made). Now, for each possible multi-battery state `B` and time point `T` one chooses the action `a` such as to minimize the cost of the action plus the value of the state to which the action leads. In terms, you have to choose `a` such as to minimize `C(a) + V(S')`, where `a` leads from `S` to `S'`. If you found this action, set the state equal to `V(S) = C(a) + V(S')`.

And so on. One does this for all possible states and stores each optimal value `V(S)` obtained in this way -- for small number of batteries `N`, this might even be feasible in practice.

Once you're ready with this, you get the optimal action in each state. For this, if one is in state `S`, one follows the same recipe as above and always picks the action `a` which minimizes `C(a) + V(S')`. This can also be done only once when the best action for each state is stored.

And then you're done -- you completely solved your problem. Or say, at least theoretically, because in practice the problem size requires too much effort and storage to do the above backward recursion and store it in a table (for the problem as specified above, I'd say this regime begins when `N~3` and larger). One therefore needs to introduce approximations.

Approximations

In using approximations, in general one sacrifices the "optimal solution" for a "good-working solution". As this can be done in several ways, this is where art begins. Or, to cite Powell, chapter 15.7.: "A successful ADP algorithm for an important problem class is, we believe, a patentable invention". Due to this, I will only sketch some possible steps that can be done here.

One class of approximation methods called aggregation uses a simplified model of the state variable. For instance, instead of including the time `T` in `5m` chunks in the state variable (288 states), one can use `1h` chunks or even a boolean value which indicates whether it's office time. Or you can use `5m` chunks only during office time plus one state out-of-office-time. And so on ... lot's of possibilities. Here one always gains a smaller tabular representation of the

Another class of approximation methods uses a parametrized representation of the value function, say a linear regression model or a neural network. In the iteration scheme above, the value functions are not stored in a table, but they are rather used as input to fit the parameters. This one replaces the often huge tabular representation by a much smaller number of parameters, but a drawback is that the fitting procedure is usually more sophisticated. (Note that in this step evolutionary algorithms can naturally be applied).

In another method, one uses basis functions which capture important states of the system. For example, in a tic-tac-toe game, you do not need all possible game states, but basis states which indicate who occupies the center and the occupied number of edges are sufficient.

Next, instead of trying to perform a full iteration over all states, one can use Monte-Carlo methods to randomly explore many but not all possible states. This is the more efficient the better heuristics exist, which let the algorithm explore meaningful states.

For other ideas as well as their practical application, consult the books mentioned above.

Ok, that became lengthy but I hope it helps to give you some idea of one possible approach. I would suggest you to design a small model using only one battery, say, and try to implement the above backward-iteration by yourself. Alternatively, in the both cited books you find several toy problems where you can get familiar with these kind of problems. Good luck with the batteries!

Problem

Original source