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?


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.