Scheduling with Discrete Resources: the Ship-loading Problem, Second Version

The ship-loading problem has a very interesting characteristic that we can actually see if we represent it as a graph where activities are vertices and the arcs between them are precedence constraints. Activities that are tightly constrained by each other will appear as a cluster of vertices connected by their constraints; other activities, more or less independent of that cluster, will appear separately (perhaps in other clusters) with few or no connecting arcs between such clusters. These clusters in the graph represent subproblems within our principal problem, subproblems that may prove more tractable than our initial problem.

For example, activity number 8 in the ship-loading problem is such that any other activity is either constrained to execute before activity number 8 or constrained to execute after activity number 8. As a result, any schedule with a minimal makespan must be such that activity number 8 executes as soon as possible. We could say that the activity number 8 is a critical activity and a cut vertex in the graph of activities.

On the basis of such a graph, we can decompose the problem into a series of smaller independent subproblems: each activity is either a cut vertex or belongs to a section separated by two cut vertices or the beginning and the end of the schedule. Consequently, it is possible to decompose the problem like this: