Home » Algorithms » Longest and Reverse Processing Time Algorithms

Longest and Reverse Processing Time Algorithms

Two simplest algorithms for parallel systems: Longest Processing Time and Reverse Processing Time with Cmax criteria, that gives approximate solution.

LPT – Longest Processing Time.

Input:
Set filled with jobs, each have p processing time.

1) Sort jobs according to p.
2) Find first free machine – assing job with longest processing time.
3) Repeat 2) as long as there are unassigned jobs.
4) Cmax = Max(Cn) where n goes from 1 to N, N is machine number.

Example:

J1 J2 J3 J4 J5 J6
p 7 4 4 3 2 2

We assign:
J1 to 1st machine (Finishing time 7).
J2 to 2nd machine (Finishing time 4).
J3 to 2nd machine (Finishing time 8).
J4 to 1st machine (Finishing time 10).
J5 to 2nd machine (Finishing time 10).
J6 to 1st machine (Finishing time 12).

Order is:
1, 4, 6 on 1st machine and 2,3,5 on 2nd.

Implementation is quite simple:
Just sort descending jobs via processing time, and then assign jobs to first free machine.
I used a int array to store finishing times for machines. Index for minimum element determines proper machine index to append job.

sortJobs(&jobs,1, &Solver::DescendingBasedOnProcessingTime);
for(int i=0; i < jobs.length(); ++i)
 {
  MachineToAssignJob = FindFreeMachine(freeTimeOnMachine, MachineAmount);
  orderedJobs[MachineToAssignJob].append(jobs[i]);
  freeTimeOnMachine[MachineToAssignJob] += jobs[i]->getTimeFromMachinePlotting(1);
 }

RTP – Reverse Processing Time.
Used with parallel systems with both Cmax and F response time criteria.

Response time is basically defined as: Fi = ci – ri.
Completion time reduced by arrival time.
So when we have all jobs with arrival time = 0, response time for job N is equal to it’s completion time.

Input:
Set filled with jobs, each have p processing time.

1) Sort jobs according LPT.
2) On each machine sort jobs in ascending order based on P.

For LPT examples approximate order is:
6, 4, 1 on 1st machine and 5, 2, 3 on 2nd.

Implementation is quite easy. Just call out LPT, and then sort each QList ascending according to processing time.

Posted in Algorithms

Comments are closed.