Single machine scheduling with profit and deadline constraints

Question

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.

• Stef: @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.
• Dmitry: 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)
• Stef: 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.
• Aishgadol: @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$
• Dmitry: 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).

Answer 1

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.

• Aishgadol: How can we be sure that when we remove job $k$ and adding job $i$ instead, $t_i$ is within $|S|$?
• pcpthm: @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$.
• Aishgadol: 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?
• pcpthm: @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.