Home » Algorithms » FIFO for one mashine sequencing

FIFO for one mashine sequencing

Simplest possible sequencing alhorithm that utilizes good ol’ Fist-In-Fist-Out queue is used to solve one mashine problems with Cmaxcriteria for jobs with specific relase time. It’s complexity is O(N log N).

Input:
Set filled with jobs, each have p processing time, and r relase time (earliest time possible to start job in question).

Algorithm consist of three simple steps:
1) Sort jobs non decreasing based on r value.
2) Compute completion time:
Ci = max{ ri, ci-1} + pi, i = 1, 2,…, n
3) Compute Cmax:
Cmax = Cn

Output: optimal job sequence.

Posted in Algorithms and tagged as

Comments are closed.