1
$\begingroup$

The problem is described as such:

Given $n$ tasks $\{J_1, \ldots , J_n\}$where each task has a deadline and a ‘profit’.

So for some $i \in \{1,\ldots , n\}$, $J_i=\{t_i,p_i\}$ where $t_i$ is the deadline to complete the task, and $p_i$ is the expected profit.

It is given that:

  • starting time is $0$
  • each task takes $1$ time to complete.
  • you can only work on a single task in every time unit.

The goal is to describe an efficient algorithm to receive a group of n task as input (as described) and finds the maximal profit subseries of tasks.

I know this problem relates to a family of problems where a machine can only perform a single task every time, and since this problem requires to find the maximal subseries, I’m inclined towards a dynamic programming approach, yet I also consider a greedy approach might do the trick.

I was unable to find a solution to the problem with such constraints.

Improve this question
$\endgroup$
9
  • $\begingroup$ @Dmitry Oops, you're right. So it's $1 \mid p_i = 1 \mid \sum w_j U_j$ and it's a lot easier. This table gives a reference for a polynomial solution: Baptiste, Philippe. "Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times." Journal of Scheduling 2.6 (1999): 245-252. $\endgroup$
    – Stef
    Nov 21, 2022 at 15:29
  • 1
    $\begingroup$ I think you can just solve it using linear programming (with variables $x_{ij}$ being "assign task $i$ to time $j$"). The only concern is whether the solution is integer, and, as I understand, this part is fine since the incidence matrix for bipartite graphs is unimodular (see e.g. theory.stanford.edu/~jvondrak/MATH233B-2017/lec3.pdf) $\endgroup$
    – Dmitry
    Nov 21, 2022 at 15:36
  • $\begingroup$ I can't access the article I mentioned, but a dynamic solution shouldn't be too complex. Note that choosing a solution for the problem basically amounts to choosing which jobs will be on-time and which jobs will be late. Indeed, once you have chosen a list of on-time jobs, you can without loss of generality order these jobs in order of due date. $\endgroup$
    – Stef
    Nov 21, 2022 at 15:38
  • $\begingroup$ @Stef I believe the profit is different for every task. Also, in the table you've shared, there is no solution described for $1|p_i=1|\sum w_j U_j$ $\endgroup$
    – Aishgadol
    Nov 21, 2022 at 16:12
  • $\begingroup$ If you think about it as "which task assign to which time", then it becomes en.wikipedia.org/wiki/Assignment_problem (if a task is assigned to the time beyond the deadline, the profit is 0). $\endgroup$
    – Dmitry
    Nov 21, 2022 at 17:00

1 Answer 1

Reset to default
1
$\begingroup$

A simple greedy algorithm is known for this problem [1].

First, sort jobs by non-decreasing order of deadline. Let $S := \emptyset$ be a variable to denote a set of jobs. Then, for each job $i$,

if |S| < t_i then:
  Add job i to S
  # Job i is scheduled at time |S|-1
else if there exists a job k in S such that p_k < p_i:
  Delete job k from S such that p_k is minimal
  Add job i to S
  # Job i is scheduled at the time job k was scheduled

By implementing the set $S$ using a priority queue, the algorithm runs in $O(n \log n)$ time. This algorithm can be generalized to the case of identical parallel machines.

The greedy algorithm can be understood as an incremental greedy algorithm for the matroid.

  • [1] Brucker, Peter. Scheduling Algorithms. 5th ed. Springer, 2007.
Improve this answer
$\endgroup$
4
  • $\begingroup$ How can we be sure that when we remove job $k$ and adding job $i$ instead, $t_i$ is within $|S|$? $\endgroup$
    – Aishgadol
    Nov 21, 2022 at 19:17
  • $\begingroup$ @Aishgadol $|S|$ is not relevant here. Let $p_i$ be the scheduled time of job $i$ then we need $p_i < t_i$. We have $p_k < t_k$ by induction. Also $t_k \leq t_i$ because we have sorted the jobs. Thus $p_i = p_k < t_k \leq t_i$. $\endgroup$
    – pcpthm
    Nov 21, 2022 at 22:16
  • $\begingroup$ I see. Thank you for sharing this solution, it truly helped me to deepen my understanding of this problem. If we were to have 2, or $k$ machines working simultaneously, how would the algorithm change? How would this affect time complexity? $\endgroup$
    – Aishgadol
    Nov 23, 2022 at 12:38
  • 1
    $\begingroup$ @Aishgadol The parallel-machine variant has almost the same algorithm. The time complexity the same. The only change is making the set $S$ to have multiplicity $k$ so the check $|S| < t_i$ will become $|S|/k < t_i$ for example. $\endgroup$
    – pcpthm
    Nov 24, 2022 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.