1
$\begingroup$

I have a problem. I want to know how to solve this in polynomial time (is it possible?).

There are $n$ customers that must be served by single machine. For every customer $C_i$, it has a profit $P_i = a_it + b_i$ where $t$ is the finish time and $a_i<0$. Yes, the profit can be negative. For every customer $C_i$, it has a service time $S_i = c_it + d_i$ where $t$ is the starting time and $c_i>0$. The problem is to find a serving order for these customers to maximize the total profit (the starting time of the first customer is $0$).

For example: \begin{align} &C_1 : P_1 = -0.5t + 35, &S_1 = 2t + 4,\\ &C_2 : P_2 = -t + 40, &S_2 = 2t + 3,\\ &C_3 : P_3 = -0.4t + 45, &S_3 = 3t + 6. \end{align}

The optimal order is $C_2, C_1, C_3$ and the profits are calculated as: \begin{align} &C_2 \text{ is done at time }3\text{ with profit }40 - 3 = 37,\\ &C_1 \text{ is done at time }3 + (2\times 3 + 4) = 13\text{ with profit }35 - 0.5\times 13 = 28.5,\\ &C_3 \text{ is done at time }13 + (3\times 13 + 6) = 58\text{ with profit }45 - 0.4\times 58 = 21.8. \end{align}

The total profit is $37 + 28.5 + 21.8 = 87.3$ (I hope I didn't make mistake calculation).

$\endgroup$

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.