I need some hints for proving the correctness/optimality of the below homework problem. It is a task-schedulding problem with deadlines and penalties. There are n tasks, each of which has a deadline and a penalty which incurs when the task is not scheduled or is scheduled to complete after the deadline. All tasks have the same length (1 hour) and may have the same deadline/penalty. The goal is to minimize the total penalties.

The algorithm:

  Sort the tasks in the order of decreasing penalties.  
  For task i = 1 to n
    Let d_i be its deadline, p_i be its penalty.
    Consider the first available time slot before d_i : # the goal is to schedule it as late as possible
      If it's empty:
        put task i there. 
        move to next task.
      If it's occupied by task j:
        If p_j >= p_i :
          throw away task i. 
          add p_i to the total penalty.
        If p_j < p_i :
          swap in task i.
          add p_j to the total penalty.
  Return the schedule and the total penalty.

I already have a hint but I still don't know where to start or what to do. The hint is to "start by considering an optimal solution and gradually transform it, preserving its optimality at each step, to the solution that the [above] algorithm produces". I just don't know what to do with an optimal solution. There may be >=1 of them and we can even assume that they result from other algorithms.

Thank you.


One should verify first that the collections of all possible feasible subsets of tasks forms a matroid structure.

  1. The empty set of tasks is feasible.

  2. If a set $X$ of tasks if feasible and $X' \subseteq X$ then $X'$ is obviously feasible.

  3. (Transfer property) Suppose $X, Y$ is feasible and $|Y| > |X|$. Then we need to show that there is $y \in Y - X$ such that $X \cup y$ is feasible. We may assume that tasks are scheduled in order of deadline. Let $y$ be the latest tasks of $Y$ not scheduled by $X$; this may be swapped to $X$.

Hence the optimal set of feasible tasks is found by adding elements one-by-one and checking for feasibility. This is essentially what this algorithm is doing. (Note that a set of tasks is feasible if, for all deadlines $t$, the number of tasks scheduled before time $t$ is at most $t$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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