Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Longest-processing-time-first scheduling
open-in-new
<p>Longest-processing-time-first (LPT) is a <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a> for <a href="/facts/Optimal_job_scheduling/XyUejB6y">job scheduling</a>. The input to the algorithm is a set of <i>jobs</i>, each of which has a specific processing-time. There is also a number <i>m</i> specifying the number of <i>machines</i> that can process the jobs. The LPT algorithm works as follows: </p> <ol><li>Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first.</li> <li>Schedule each job in this sequence into a machine in which the current load (= total processing-time of scheduled jobs) is smallest.</li></ol> <p>Step 2 of the algorithm is essentially the <a href="/facts/List_scheduling/qUscTqbx">list-scheduling</a> (LS) algorithm. The difference is that LS loops over the jobs in an arbitrary order, while LPT pre-orders them by descending processing time. </p><p>LPT was first analyzed by <a href="/facts/Ronald_Graham/ukKzczTL">Ronald Graham</a> in the 1960s in the context of the <a href="/facts/Identical-machines_scheduling/lwNSXMs6">identical-machines scheduling</a> problem. Later, it was applied to many other variants of the problem. </p><p>LPT can also be described in a more abstract way, as an algorithm for <a href="/facts/Multiway_number_partitioning/6dUsX2HI">multiway number partitioning</a>. The input is a set <i>S</i> of numbers, and a positive integer <i>m</i>; the output is a partition of <i>S</i> into <i>m</i> subsets. LPT orders the input from largest to smallest, and puts each input in turn into the part with the smallest sum so far. </p>