Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  vonbrand Jan 29 '13 at 19:11
    
@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. –  Ioannis Souldatos Jan 29 '13 at 19:36
    
You ignore changes of cost over time as well as costs implied by *not*renewing (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? –  Raphael Jan 30 '13 at 13:11
    
@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. –  Ioannis Souldatos Jan 30 '13 at 16:32
    
@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$). –  Ioannis Souldatos Jan 30 '13 at 16:37
show 2 more comments

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
This will do. Thank you. –  Ioannis Souldatos Jan 30 '13 at 16:42
add comment

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).

share|improve this answer
    
This would do the job, but I want something that combines the three factors. I edited the post to be make it more precise. –  Ioannis Souldatos Jan 29 '13 at 20:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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