Lawler's algorithm is an efficient algorithm for solving a variety of constrained scheduling problems, particularly single-machine scheduling. It can handle precedence constraints between jobs, requiring certain jobs to be completed before other jobs can be started. It can schedule jobs on a single processor in a way that minimizes the maximum tardiness, lateness, or any function of them.
Definitions There are n jobs. Each job is denoted by i {\displaystyle i} and has the following characteristics:
Processing-time, denoted by pi; Due time, denoted by d i {\displaystyle d_{i}} . Cost function, denoted by g i {\displaystyle g_{i}} ; it is a weakly-increasing function of the time job i completes its execution, denoted by F i {\displaystyle F_{i}} . The objective function is m i n m a x 0 ≤ i ≤ n g i ( F i ) {\displaystyle min\,max_{0\leq i\leq n}\,g_{i}(F_{i})} . Some special cases are:
When g i ( F i ) = F i − d i = L i {\displaystyle g_{i}(F_{i})=F_{i}-d_{i}=L_{i}} , the objective function corresponds to minimizing the maximum lateness When g i ( F i ) = m a x ( F i − d i , 0 ) {\displaystyle g_{i}(F_{i})=max{(F_{i}-d_{i},0)}} , the objective corresponds to minimizing the maximum tardiness.
Algorithm The algorithm builds the schedule back to front. For each scheduling step, it looks only at the tasks that no other tasks depend on, and puts the one with the latest due date at the end of the schedule queue. Then it repeats this process until all jobs are scheduled. The algorithm works by planning the job with the least impact as late as possible. Starting at t = ∑ p j {\displaystyle t=\sum p_{j}} that p j {\displaystyle p_{j}} is the processing time of job j {\displaystyle j} .
S {\displaystyle S} set of already scheduled jobs (at start: S = ∅ {\displaystyle \emptyset } )
J {\displaystyle J} set of jobs whose successors have been scheduled (at start: all jobs without successors)
t {\displaystyle t} time when the next job will be completed (at start: t = ∑ p j {\displaystyle t=\sum p_{j}} ) while J ≠ ∅ {\displaystyle J\neq \emptyset } do select j ∈ J {\displaystyle j\in J} such that f j ( t ) = m i n k ∈ J f k ( t ) {\displaystyle f_{j}(t)=min_{k\in J}f_{k}(t)}
schedule j {\displaystyle j} such that it completes at time t {\displaystyle t}
add j {\displaystyle j} to S {\displaystyle S} , delete j {\displaystyle j} from J {\displaystyle J} and update J {\displaystyle J} . t = t − p j {\displaystyle t=t-p_{j}}
end while
Example 1 Assuming there are three jobs: t1, t2, and t3, with the following precedence constraints:
t1-> t2, t1 must finish before t2 t1-> t3, t1 must finish before t3 And the following deadlines (due date in a month)
t1: 2nd day t2: 5th day t3: 8th day Now we construct the required set of jobs:
S = {empty}, initially empty set of scheduled jobs J = {t2, t3}, the set of jobs whose successors have been scheduled or jobs without successors. t2 and t3 have no successors. Repeat the following steps until J is empty:
select a job j in J, so its due date is the latest, in this example, it is t3 with a due date 8th. move j from J to S's front, now J = {t2}, S={t3}. update J to add any new job whose successors have been scheduled. There is none this time. Do the next round:
select a job j in J, so its due date is the latest. It is t2 with due date 5th this time. move j from J to S's front, now J = {empty}, S={t2, t3} update J to add any new job whose successors have been scheduled, now J= {t1} since both t2 and t3 have been scheduled. Do the next round:
… excerpt ends here. Continue reading the full article.
