# Time dependent scheduling with profit

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