Greedy algorithm: highest value first vs earliest deadline first

Question

Assume we have a set of n jobs to execute, each of which takes unit time. At any time we can serve exactly one job. Job i, 1<=i<=n earns us a profit if and only if it is executed no later than its deadline.

We can a set of jobs feasible if there exists at least one sequence that allows each job in the set to be performed no later than their deadline. "Earliest deadline first" is feasible.

Show that the greedy algorithm is optimal: Add in every step the job with the highest value of profit among those not yet considered, provided that the chosen set of jobs remains feasible.

MUST DO THIS FIRST: show first that is always possible to re-schedule two feasible sequences (one computed by Greedy) in a way that every job common to both sequences is scheduled at the same time. This new sequence might contain gaps.

UPDATE

I created an example that seems to disprove the algorithm:

Assume 4 jobs:

• Job A has profit 1, time duration 2, deadline before day 3;
• Job B has profit 4, time duration 1, deadline before day 4;
• Job C has profit 3, time duration 1, deadline before day 3;
• Job D has profit 2, time duration 1, deadline before day 2.

If we use greedy algorithm with the highest profit first, then we only get job B & C. However, if we do deadline first, then we can get all jobs and the order is CDB

Not sure if I am approaching this question in the right way, since I created an example to disprove what the question wants

Answer 1

This problem looks like Job Shop Scheduling, which is NP-complete (which means there's no optimal greedy algorithm - despite that experts are trying to find one since the 70's). Here's a video on a more advanced form of that use case that is being solved with a Greedy algorithm followed by Local Search.

If we presume your use case can indeed be relaxed to Job Shop Scheduling, than there are many optimization algorithms that can help, such as Metaheuristics (including Local Search such as Tabu Search and Simulated Annealing), (M)IP, Dynamic Programming, Constraint Programming, ... The reason there are so many choices, is because none are perfect. I prefer Metaheuristics, as they out-scale the others in all the research challenges I've seen.

Answer 2

In fact, neither "earliest deadline first", "highest profit first" nor "highest profit/duration first" are correct algorithm...

Assume 2 jobs:

• Job A has profit 1, time duration 1, deadline before day 1;
• Job B has profit 2, time duration 2, deadline before day 2;

Then "earliest deadline first" fails to get correct answer. Correct answer is B.

Assume another 5 jobs:

• Job A has profit 2, time duration 3, deadline before day 3;
• Job B has profit 1, time duration 1, deadline before day 1;
• Job C has profit 1, time duration 1, deadline before day 2;
• Job D has profit 1, time duration 1, deadline before day 3;
• Job E has profit 1, time duration 1, deadline before day 4;

Then "highest profit first" fails to get correct answer. Correct answer is BCDE.

Assume another 4 jobs:

• Job A has profit 6, time duration 4, deadline before day 6;
• Job B has profit 4, time duration 3, deadline before day 6;
• Job C has profit 4, time duration 3, deadline before day 6;
• Job D has profit 0.0001, time duration 2, deadline before day 6;

Then "highest profit/duration first" fails to get correct answer. Correct answer is BC (Thanks for @dognose's counter-example, see comment).

One correct algorithm is Dynamic Programming:

First order by deadline ascending. dp[i][j] = k means within the first i jobs and within j time units we can get k highest profit. Then initially dp[0][0] = 0.

Jobs info are stored in 3 arrays: profit are stored in profit[i], 1<=i<=n, time duration are stored in time[i], 1<=i<=n, deadline are stored in deadline[i], 1<=i<=n.

  // sort by deadline in ascending order
  ...
  // initially 2 dimension dp array are all -1, -1 means this condition unreachable
  ...
  dp[0][0] = 0;
  int maxDeadline = max(deadline); // max value of deadline
  for(int i=0;i<n;i++) {
      for(int j=0;j<=maxDeadline;j++) {
          // if do task i+1 satisfy deadline condition, try to update condition for "within the first i+1 jobs, cost j+time[i+1] time units, what's the highest total profit will be"
          if(dp[i][j] != -1 && j + time[i+1] <= deadline[i+1]) {
              dp[i+1][j+time[i+1]] = max(dp[i+1][j+time[i+1]], dp[i][j] + profit[i+1]);
          }
      }
  }
  // the max total profit can get is max value of 2 dimension dp array

The time/space complexity (which is n*m, n is job count, m is maximum deadline) of DP algorithm is highly dependent on how many jobs and the maximum deadline. If n and/or m is rather large, it maybe difficult to get answer, while for common use, it will work well.

Answer 3

The problem is called Job sequencing with deadlines, and can be solved by two algorithms based on greedy strategy:

1. Sort input jobs decreasing on profit. For every job put it in list of jobs of solution sorted increasingly on deadline. If after including a job some jobs in solution has index grater than deadline, do not include this job.
2. Sort input jobs decreasing on profit. For every job put it in the list of job of solution on the last possible index. If there is no free index less or equal to the job deadline, do not include the job.