Scheduling to minimize lateness

The problem can be stated as follows :

“Given a set of n jobs all of which must be scheduled on a single resource such that all jobs arrive at time s and each job has a deadline di and a length ti, minimize the maximum lateness of the resulting schedule.”

We need to assign a start time si to each job i. Jobs are allowed to be late i.e., a job i may finish at time fi = si + ti > di. If job i is late, its lateness is defined to be li = fi – di. Otherwise, li = 0. So the objective is to find a schedule that minimizes the maximum lateness, L = maxi li.

Continue reading

Articulation Points or Cut Vertices in a Graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. It can be thought of as a single point of failure. Any graph that contains an articulation point is inherently fragile because deleting that single vertex causes a loss of connectivity between other nodes. If a graph does not have an articulation point, then it is said to be biconnected.

Continue reading