Question

Find all possible orders for completing the tasks in the development project in Example 27.

Short answer

All orderings which respect the conditions

\(\begin{array}{l}A \prec C \prec E < B < D < F < G,\\A < E < C < B < D < F < G,\\C < A < E < B < D < F < G,\\C < E < A < B < D < F < G,\\E < A < C < B < D < F < G,\\E < C < A < B < D < F < G,\\A \prec C < B < E < D < F < G,\\C < A < B < E < D < F < G,\\A \prec C \prec B \prec D < E < F < G,\\C < A < B < D < E < F < G,\\A < C < E < B < F < D < G,\\A < E < C < B < F < D < G,\\C < A < E < B < F < D < G,\\C < E < A < B < F < D < G,\\E < A < C < B < F < D < G,\\E < C < A < B < F < D < G,\\A < C < B < E < F < D < G,\\C < A < B < E < F < D < G.\end{array}\)

Step-by-step solution

Given data

\({\rm{R}}\) is the partial order on the set of tasks \(T = \{ A,B, \ldots ,G\} \).

Concept used of compatibility of total order

A total order\( \prec \)is compatible with the partial order\(R\)if\(a < b\)whenever\(aRb\).

Find the compatible total order

There are a few restrictions, but there are many choices, so we will get many (18) compatible total orderings. Note that \({\rm{A}}\) and \({\rm{C}}\) must precede \({\rm{B}};{\rm{B}}\) and \({\rm{E}}\) must precede \({\rm{F}};{\rm{B}}\) must precede \({\rm{D}}\); and \({\rm{G}}\) must come last. We can therefore make the following list

\(\begin{array}{l}A \prec C \prec E < B < D < F < G,\\A < E < C < B < D < F < G,\\C < A < E < B < D < F < G,\\C < E < A < B < D < F < G,\\E < A < C < B < D < F < G,\\E < C < A < B < D < F < G,\\A \prec C < B < E < D < F < G,\\C < A < B < E < D < F < G,\\A \prec C \prec B \prec D < E < F < G,\\C < A < B < D < E < F < G,\\A < C < E < B < F < D < G,\\A < E < C < B < F < D < G,\\C < A < E < B < F < D < G,\\C < E < A < B < F < D < G,\\E < A < C < B < F < D < G,\\E < C < A < B < F < D < G,\\A < C < B < E < F < D < G,\\C < A < B < E < F < D < G.\end{array}\)