I have this problem

A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of running machine $i$ is $f_i +m_i·q$ where $f_i$ is the fixed cost of running the machine and $m_i$ is the marginal cost of servicing one job on the machine (thus $m_i·q$ is the marginal cost of servicing $q$ jobs). Assume that $f_1 ≤ f_2 ≤ ···≤ f_n$ and that $m_1 ≤ m_2 ≤···≤ m_n$. The firm wishes to find a subset of the machines that can service all the jobs at the minimum total cost. Show how this problem can be formulated as a shortest path problem.

I assume, possibly will have to show, that the $q_j$ jobs of type $j$ are all done by the same machine. Here is one of the most promising attempts that I got so far:

Here is the first graph implementation graph implementation

So basically, we have a directed tree going from right to left. At the level 0 edge, are done $q_n$ jobs of type $n$ by the machine $[n]$ and on the edge is the cost of this operation. Further, for completing the $q_{n-1}$ jobs of type $n-1$, we can choose either the machine $[n]$ or $[n-1]$ with the associated costs over the edges. And so on. The problem is that already at the level 4, if I use the machine $[n-1]$ for completing $q_{n-3}$ jobs of type $n-3$ after using machine $[n-2]$ I don't know if the machine $[n-1]$ was used before. So I don't know beforehand the cost of taking the edge between $[n-2]$ at level 3 and $[n-1]$ at level 4.

The same problem is highlighted at the level 5 for the machine $[n-2]$ by two zigzagging paths, one using the machine $[n-2]$ and the other avoiding it.

The number of edges of this tree has a growth of order $n^3$ and the number of vertices has a growth of order $n^2$. So this solution still looks feasible if we manage to patch the mentioned problems.

So here are my questions:

  1. What is the common name given to this class of problems? (if it exists)
  2. How can my solution attempt be fixed? (if it can be done)
  3. Otherwise, how the problem can be solved?

Thank you very much in advance for your time and help!


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.