# Single machine scheduling with profit and deadline constraints

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.

• @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.
– Stef
Nov 21, 2022 at 15:29
• 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) Nov 21, 2022 at 15:36
• 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.
– Stef
Nov 21, 2022 at 15:38
• @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$ Nov 21, 2022 at 16:12
• 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). Nov 21, 2022 at 17:00

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:
# 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

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.
• How can we be sure that when we remove job $k$ and adding job $i$ instead, $t_i$ is within $|S|$? Nov 21, 2022 at 19:17
• @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$. Nov 21, 2022 at 22:16
• 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? Nov 23, 2022 at 12:38
• @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. Nov 24, 2022 at 3:15