Jorge Quitério Search
Technology

The design structure matrix and task sequencing

A project plan is a list, but a development project is a network with feedback loops. The design structure matrix represents those loops on one page, and a graph algorithm orders the tasks to minimise rework. The example is a small satellite payload project.

Every engineering project plan I have seen is a list or a Gantt chart: task A, then task B, then task C. Every engineering project I have worked on was a network with loops: the thermal design changes the power budget, which changes the payload, which changes the thermal design. The plan leaves the loops out, and the project discovers them, usually late and at some cost.

Planning a wedding has the same structure. The venue limits the number of guests, the number of guests sets the catering budget, and the budget limits the choice of venue. None of the three can be settled first and left alone; they are decided together. The invitations, the seating plan and the flowers, by contrast, follow in sequence once those three are fixed.

The design structure matrix (DSM) is a way to put the loops on the plan. It is a simple square table recording which task needs information from which other task, and it comes with an algorithm that reorders the work to expose the loops and minimise the rest. This article addresses how to sequence tasks that depend on each other cyclically.

Don Steward published the method in 1981 under the name design structure system, for organising the solution of large systems of equations and the design of complex systems. Eppinger, Whitney, Smith and Gebala (1994) brought it into product development as a model of how engineering tasks exchange information, and Eppinger and Browning's Design Structure Matrix Methods and Applications (2012) is the reference text, covering product, organisation and process architectures. In de Weck's roadmapping method, a DSM links each roadmap to the others it depends on, as described in technology roadmaps as quantitative models. The reordering step is a classic of graph theory: the strongly connected components of a directed graph, which Tarjan (1972) showed how to find in a single depth-first search.

Reading a DSM

The tasks are listed in their planned order along both the rows and the columns. In row ii, a mark is placed in column jj if task ii needs information from task jj. Then:

  • a mark below the diagonal means the information comes from a task done earlier: it flows forward, as planned;
  • a mark above the diagonal means the information comes from a task scheduled later: the work must start from an assumption and be revised when the real input arrives.

The marks above the diagonal are the project's iterations. Some can be removed by reordering. Others cannot, because the tasks genuinely depend on each other in a cycle.

Partitioning

The reordering is called partitioning. Treat tasks as nodes and dependencies as arrows. A set of tasks in which each can reach every other through the arrows is a strongly connected component: a block of mutual dependence that no ordering can untangle. Collapse each block into a single node and what remains has no cycles, so it can be put in an order where every task comes after everything it needs. Inside each block, choose the order that leaves the fewest marks above the diagonal; those remaining marks are the iterations that must be planned for.

The figure below reorders the project. Reordering removes every feedback mark except those inside coupled blocks, and the coupled blocks are the real iterations of the project.

The example is a small satellite payload development with eight tasks. Payload, power, thermal and structure depend on one another, as they do in practice.

  1. Initial order. In the scrambled order there are 11 feedback marks, each representing work based on an assumption.
  2. Partitioning. Press "Sequence". Requirements come first, integration and test last, and payload, power, thermal and structure collapse into one coupled block of four tasks. Feedback marks drop from 11 to 3, all of them inside the block.
  3. Removing a dependency. Click the dot where the payload design needs the power budget, to remove that dependency (for instance by fixing a power allocation early), then sequence again. The block shrinks or changes shape. This is what systems engineers do with margins and interface agreements: they remove dependencies deliberately. A couple that fixes the total budget before visiting venues does the same, turning a three-way loop into a sequence.
  4. Additional dependency. Add a dependency from requirements to environmental test (a test result that forces new requirements) and sequence again. Now the whole project is one block of eight. A project in this state cannot be scheduled reliably.

Optimality of partitioning. In any ordering, each pair of tasks in the same strongly connected component lies on a directed cycle, so at least one arrow of that cycle points backwards: no ordering removes all feedback inside a component. Between components the condensed graph is acyclic, so a topological order exists in which every arrow between different components points forward. Partitioning therefore attains zero feedback between blocks, the minimum possible, and leaves only the unavoidable feedback within them. Tarjan's algorithm finds the components and, as a by-product, emits them in reverse topological order: dependencies first.

Before a complex development is scheduled, its DSM should be drawn. The blocks show where the project needs integrated teams, co-location, early interface agreements and time buffers. The rest of the work can run in sequence.

References

  1. R. Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1(2), 146-160, 1972.
  2. D. V. Steward, "The design structure system: A method for managing the design of complex systems", IEEE Transactions on Engineering Management, EM-28(3), 71-74, 1981.
  3. S. D. Eppinger, D. E. Whitney, R. P. Smith and D. A. Gebala, "A model-based method for organizing tasks in product development", Research in Engineering Design, 6(1), 1-13, 1994.
  4. S. D. Eppinger and T. R. Browning, Design Structure Matrix Methods and Applications, MIT Press, 2012.
  5. O. L. de Weck, Technology Roadmapping and Development: A Quantitative Approach to the Management of Technology, Springer, 2022.