1
$\begingroup$

I've been studying a problem of the following kind:

$T = 1,\ldots, \max{T}$ is a discrete period of time, and we can use every production unit $i \in I$ at most twice. Every unit has a fixed attribute $s_i$ - kind of its size - and another productivity attribute $p(t')$ which is increasing on idle time. When $i$ is used, it provides a benefit $b(t') \cdot s_i$ which depends on the time $t'$ it's been idle and is the same function over all units, increasing on idle time $t'$. Just to be more explicit, if we use $i$ at time $t$ then $p_i$ and $b(t)$ are rebooted to 0 and start to increase again in $t+1$. Note that $p$ and $b$ are the same for all units.

And the following conditions must be fulfilled:

  • There's a minimum $C_{min}$ and maximum $C_{max}$ capacity which must be respected at every time: the sum of $s_i$ that are used at $t$ must be between $C_{min}$ and $C_{max}$. These parameters are constant along time.
  • There's a desired regularity in production, within a percentage $f$: $$ (1-f) \cdot Total_p(t-1) \leq Total_p(t) \leq (1+f) \cdot Total_p(t-1) $$ where $Total_p(t)$ is the sum of $p_i(t)s_i$ for the $i$ that are used at time $t$. I got an integer programming formulation and as expected this constraint is the one that makes the problem more difficult to solve using branch and cut.
  • As mentioned above, every unit can be used once, twice or not at all.
  • Initially, each unit has its starting idle time $t_i$.
  • There's a minimum and maximum idle time, $T_{min}$ and $T_{max}$, which must be respected. If unit $i$ is used (for the first and/or second time), it must be when idle time is between those values. $T_{max}$ is roughly $2 \times \max{T}$, hence the maximum 2 uses per unit.

The objective is to maximize the total monetary benefit, which is the sum of benefits over $T$. As stated before, if unit $i$ has been idle for a period $t'$, then its production if used at time $t$ will be $b(t')\cdot s_i$ (note that there's no direct effect into $t$ on this).

This problem has some similarities to scheduling and assignment problems, and I was able to design a simple greedy heuristic with some success, but am not aware if this category of problems has a name, or if it has been studied in the OR literature before. Pretty sure the result of that heuristic could be improved using ideas from local search, too. Have problems with many of the mentioned characteristics been studied before (most likely in the fields of machine scheduling or production planning) and is there a name for this kind of regularity constraint? Do you know any useful references on how this could be approached? I'm more interested in adapting/designing heuristics than in MIP models (already have a formulation) but all suggestions and pointers are welcome. In particular I have the intuition that techniques such as greedy algorithms, local search and dynamic programming could be fruitful.

$\endgroup$
4
  • $\begingroup$ Your last bullet oint ("hence the maximum 2 uses per unit") does not compute. Did you mean that $T_{min} \approx \frac{1}{2} \times \max T$? $\endgroup$ – prubin Dec 26 '20 at 22:34
  • $\begingroup$ @dhasson, Would you say please, what you mean by "Initially, each unit has its starting idle time $t_i$"? Is it something like a setup time? Also, "productivity attribute $p_i(t)$ which is increasing on idle time", do you try measuring the productivity of each unit? $\endgroup$ – A.Omidi Dec 27 '20 at 8:34
  • $\begingroup$ @prubin I agree that the condition you mention would suffice. But in this case it's $T_{max} \approx \max{T}$ to allow for units with low starting idle time to be used twice, taking the simplification (omitting a possible third use) based on the system's data: as productivity potential grows over time and productivity at age $T_{min} is negligible (relative to higher times), we wouldn't want to use a unit e.g. 3x with small times between subsequent instants. $\endgroup$ – dhasson Dec 27 '20 at 21:14
  • $\begingroup$ @A.Omidi the system being modelled has been working for some time, so the starting idle times are according to the past, values known. Yes the function $p(t)$ is also known and measured. $\endgroup$ – dhasson Dec 27 '20 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.