Intro

The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its processing time) over the set of jobs. Jobs must be processed on a sequence of machines in a particular order. An operation refers to a particular job being processed on a particular machine.

Representation

A disjunctive graph is typically used to represent the problem of minimising makespan. Each node in the graph is labelled $(i,j)$ where $i$ refers to the job, and $j$ to the machine on which the job is to be run. Conjunctive arrows between nodes indicate precedence constraints for a particular job. Each conjunctive edge is given a weight, corresponding to the processing time $P_{i}$ for the particular operation $O_{i}$ at the base of the edge. Disjunctive edges are placed between operations that take place on the same machine. An example of two simple jobs is given below:

Note that $J_{1}$ is comprised of the upper row of nodes, and $J_{2}$ the lower row.

Problem

My problem is with the terminology used to describe how to solve the JSP. The book "Scheduling Theory, Algorithms, and Systems" (Pinedo, 2008) states on page 181 that:

A feasible schedule corresponds to a selection of one disjunctive arc from each pair such that the resulting directed graph is acyclic

However, if I do just that, I can derive a graph that looks something like this:

Now, it is said that:

The makespan of a feasible schedule is determined by the longest path in G(D) from the source U to the sink V

And if I sum the longest weighted path, I can indeed derive a "makespan" value. However, I still don't get why this is a "feasible schedule". Because I don't really have a schedule at all. The path doesn't give me an ordering for how to execute the callbacks. That is because the path necessarily does not visit every operation. Meaning that it does not give a feasible schedule at all.

Verdict

In light of what I have described above, my question is: How can I derive the full sequence of operations to perform from the disjunctive graph model of the job shop problem?