Lawler's algorithm

From formulasearchengine
Revision as of 21:37, 29 May 2013 by en>Simmscmi (Undid revision 552023292 by 65.175.3.10: most probably the algorithm was devised by the computer scientist Eugene Lawler, not the wrestler Jerry "The King" Lawler)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Lawler’s algorithm is a powerful technique for solving a variety of constrained scheduling problems.[1] The algorithm handles any precedence constraints. It schedules a set of simultaneously arriving tasks on one processor with precedence constraints to minimize maximum tardiness or lateness. Precedence constraints occur when certain jobs must be completed before other jobs can be started.

Objective Functions

The objective function is assumed to be in the form , where is any nondecreasing function and is the flow time.[2] When , the objective function corresponds to minimizing the maximum lateness, where is due time for job and lateness of job . Another expression is , which corresponds to minimizing the maximum tardiness.

References

  1. Steven Nahmias. Production and Operations Analysis. 2008. ISBN 978-0-07-126370-2
  2. Joseph Y-T. Leung. Handbook of scheduling: algorithms, models, and performance analysis. 2004. ISBN 978-1-58488-397-5

Additional readings

  • Michael Pinedo. Scheduling: theory, algorithms, and systems. 2008. ISBN 978-0-387-78934-7
  • Conway, Maxwell, Miller. Theory of Scheduling. 1967. ISBN 0-486-42817-6