3
$\begingroup$

I am looking for algorithms to prioritize equipment renewals.

Input: (years since last renewal, cost of renewal, importance of renewal).

Output: An ordering of the equipment according to which it will be renewed.

I do not know if there are any algorithms for this particular problem. If you have any idea how to fit this problem into a more general context, that would be useful too.

A way to rephrase the problem:

You have $n$ pieces of equipment $E_1,\ldots,E_n$. For each piece $E_i$ you have a triple $(\text{age}_i,\text{cost}_i,\text{importance}_i)$. At the beginning of the year you have $X$ amount of money. You want to spend these money in order to minimize the function $\sum_i \text{age}_i\cdot \text{importance}_i$ at the end of the year. So, during the year you have to select a subset $S$ of $\{1,\ldots,n\}$ such that: $$\sum_{i\in S} \text{cost}_i\le X \text{ (cost constraint)}$$ and the sum $$\sum_{i\in S} \text{age}_i\cdot \text{importance}_i$$ is maximal among all subsets of $\{1,\ldots,n\}$ that satisfy the cost constraint.

Any help?

$\endgroup$
7
  • $\begingroup$ Any other data? As it stands, the obvious optimal schedule is don't change anything, as they won't ever break/be left without maintenance/... I.e., you give no reaon to change anything. $\endgroup$
    – vonbrand
    Jan 29, 2013 at 19:11
  • $\begingroup$ @vonbrand: The reason to change anything is the importance factor. That's a good comment. I will edit the post to make it more specific. $\endgroup$ Jan 29, 2013 at 19:36
  • $\begingroup$ You ignore changes of cost over time as well as costs implied by notrenewing (e.g. failure). I wonder whether that's a problem of your practical circumstances or your model. Or do you consider this a theoretical problem? $\endgroup$
    – Raphael
    Jan 30, 2013 at 13:11
  • $\begingroup$ @Raphael: You are right costs will change over time, but let's assume that you split time into time intervals (years in the above formulation) during which the cost does not change. That's for the sake of simplification. $\endgroup$ Jan 30, 2013 at 16:32
  • $\begingroup$ @Raphael: If equipment fails, then the importance factor increases. If the equipment is absolutely necessary, importance becomes a very large positive number (you can even allow $\infty$). $\endgroup$ Jan 30, 2013 at 16:37

2 Answers 2

4
$\begingroup$

Given the clarification to the question, it is a 0-1 knapsack problem (your knapsack is the money available, the value is the objective function), and look for ways to solve that one, for example following the Wikipedia lead.

Edit: A simple approximate algorithm would be just sort equipment on increasing cost per unit (age * importance), and in that order include each if it fits (doesn't run over maximal cost). In the case of continuous knapsack (i.e., can include a fraction of a item) that strategy is optimal. Should work fine if there are many items, and the data isn't too spread out.

$\endgroup$
0
1
$\begingroup$

It all depends on how you define how you decide a an equipment is to be renewed. But at the end, you may sort the lists lexicographically. That is, define a comparison function that takes as input two sets $X = (x _1, ..., x_k)$ and $Y = (y _1, ..., y _k)$, it will return true if $X \succ Y$ and false otherwise, where $X \succ Y$ if:

  • $x _1 \succ y _1$ or:
  • if there is a $j$ s.t. $1 < j \leq k$, $x _j \succ y _j$ and $x _i = y _i$ for each $1 \leq i < j$.

Use this function with any sorting algorithm you know. (but instead of sorting numbers, you sort lists according to the set comparison function you define).

$\endgroup$
1
  • $\begingroup$ This would do the job, but I want something that combines the three factors. I edited the post to be make it more precise. $\endgroup$ Jan 29, 2013 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.