2
$\begingroup$

Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for finishing the respective job before the deadline), processing time $t_i$ and deadline time $b_i$. We can perform only one job in a moment with no interruptions. Our goal is to plan the order of performing the jobs with the highest total value of finished jobs before the deadline.

Formally, we have sets $S=\{1, 2, \ldots, n\}, C=\{c_1, c_2, \ldots, c_n\}, T=\{t_1, t_2, \ldots, t_n\}, B=\{b_1, b_2, \ldots, b_n\}$. We are looking for the subset $S_1 \subseteq S$ with an order $\pi$ on its elements such that $\{\pi_1, \pi_2, \ldots \pi_k\} = S_1$ and the following restrictions are performed: $$ \forall l \in \{1, 2, \ldots, k\}: b_{\pi_l} \geqslant \sum_{i=1}^{l} t_{\pi_i} $$ $$ \sum_{i=1}^k c_{\pi_i} \longrightarrow \max $$

I'm interested in the complexity of this task. It's easy to see that this problem is $NP$-hard if parameters are given in a binary representation (because in the case of all equal parameters $b_i$ we can get the Knapsack problem). So my questions are:

  1. Does this task belong to $P$ if numbers are given in unary form?
  2. What approximation algorithms are known for this task, are there any PTAS or FPTAS?
$\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.